Polynomial-time compression

Judy Goldsmith, Kenneth Kunen, Lane A. Hemachandra

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


This paper studies the class of infinite sets that have minimal perfect hash functions-one-to-one onto maps between the sets and ∑*-computable in polynomial time. We will call such sets P-compressible. We show that all standard NP-complete sets are P-compressible, and give a structural condition, E = ∑2E, sufficient to ensure that all infinite NP sets are P-compressible. On the other hand, we present evidence that some infinite NP sets, and indeed some infinite P sets, are not P-compressible: if an infinite NP set A is P-compressible, then A has an infinite sparse NP subset, yet we construct a relativized world in which some infinite NP sets lack infinite sparse NP subsets. This world is built upon a result that is of interest in its own right; we determine optimally-with respect to any relativizable proof technique-the complexity of the easiest infinite sparse subsets that infinite P sets are guaranteed to have.

Original languageEnglish
Pages (from-to)18-39
Number of pages22
JournalComputational Complexity
Issue number1
StatePublished - Mar 1992


  • Subject classifications: 68Q15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Mathematics
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Polynomial-time compression'. Together they form a unique fingerprint.

Cite this