## Abstract

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 = ∑_{2}^{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.

Original language | English |
---|---|

Pages (from-to) | 18-39 |

Number of pages | 22 |

Journal | Computational Complexity |

Volume | 2 |

Issue number | 1 |

DOIs | |

State | Published - Mar 1992 |

## Keywords

- Subject classifications: 68Q15

## ASJC Scopus subject areas

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