caa a22 4500 469033894 CHVBK 20180323132751.0 cr unu---uuuuu 170328e19920301xx s 000 0 eng 10.1007/BF01276437 doi (NATIONALLICENCE)springer-10.1007/BF01276437 Polynomial-time compression [Elektronische Daten] [Judy Goldsmith, Kenneth Kunen, Lane Hemachandra] This paper studies the class ofinfinite 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 = ∑ 2 E , sufficient to ensure thatall 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 setA is P-compressible, thenA 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. Birkhäuser Verlag, 1992 68Q15 nationallicence Goldsmith Judy Department of Computer Science, University of Manitoba, R3T 2N2, Winnipeg, Manitoba, Canada aut Kunen Kenneth Computer Sciences Department, University of Wisconsin, 53706, Madison, WI aut Hemachandra Lane Department of Computer Science, University of Rochester, 14627, Rochester, NY aut computational complexity Birkhäuser-Verlag 2/1(1992-03-01), 18-39 1016-3328 2:1<18 1992 2 37 https://doi.org/10.1007/BF01276437 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01276437 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Goldsmith Judy Department of Computer Science, University of Manitoba, R3T 2N2, Winnipeg, Manitoba, Canada aut NATIONALLICENCE 700 1- Kunen Kenneth Computer Sciences Department, University of Wisconsin, 53706, Madison, WI aut NATIONALLICENCE 700 1- Hemachandra Lane Department of Computer Science, University of Rochester, 14627, Rochester, NY aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag 2/1(1992-03-01), 18-39 1016-3328 2:1<18 1992 2 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer