Polynomial-time compression
From MaRDI portal
Publication:1198955
DOI10.1007/BF01276437zbMath0752.68039MaRDI QIDQ1198955
Hemaspaandra, Lane A., Judy Goldsmith, Kenneth Kunen
Publication date: 16 January 1993
Published in: Computational Complexity (Search for Journal in Brave)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Avoiding simplicity is complex, Scalability and the isomorphism problem, 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
