Polynomial-time compression

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 = ∑₂^E, 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.