Polynomial-time compression

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)

zbMATH Keywords

infinite sets; minimal perfect hash functions

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

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