Polynomial-time compression
From MaRDI portal
Publication:1198955
DOI10.1007/BF01276437zbMath0752.68039OpenAlexW2036028771MaRDI QIDQ1198955
Judy Goldsmith, Kenneth Kunen, Hemaspaandra, Lane A.
Publication date: 16 January 1993
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01276437
Related Items (7)
Resource-bounded kolmogorov complexity revisited ⋮ Scalability and the isomorphism problem ⋮ Polynomial-time axioms of choice and polynomial-time cardinality ⋮ Recursion-theoretic ranking and compression ⋮ Avoiding simplicity is complex ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ Characterizing the existence of one-way permutations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The strong exponential hierarchy collapses
- Oracle-dependent properties of the lattice of NP sets
- Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
- On the complexity of ranking
- A low and a high hierarchy within NP
- The complexity of facets (and some facets of complexity)
- Reductions among polynomial isomorphism types
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Bounded query machines: on NP and PSPACE
- Bounded query machines: on NP( ) and NPQUERY( )
- On sets polynomially enumerable by iteration
- Relative complexity of checking and evaluating
- The polynomial-time hierarchy
- Computation times of NP sets of different densities
- The complexity of ranking simple languages
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- Complexity Measures for Public-Key Cryptosystems
- The Complexity of Enumeration and Reliability Problems
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Relating Equivalence and Reducibility to Sparse Sets
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Perfect hashing functions
- Dynamic Perfect Hashing: Upper and Lower Bounds
- P-Printable Sets
This page was built for publication: Polynomial-time compression
