## 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 show that all standard NP-complete sets have polynomialtime computable minimal perfect hash functions, and give a structural condition, E = Σ^{E}_{2} sufficient to ensure that all infinite NP sets have polynomialtime computable minimal perfect hash functions. On the other hand, we present evidence that some infinite NP sets, and indeed some infinite P sets, do not have polynomial-time computable minimal perfect hash functions: if an infinite NP set A has polynomial-time computable perfect minimal hash functions, 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 |
---|---|

Title of host publication | Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings |

Editors | Somenath Biswas, Kesav V. Nori |

Pages | 212-223 |

Number of pages | 12 |

DOIs | |

State | Published - 1991 |

Event | 11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991 - New Delhi, India Duration: Dec 17 1991 → Dec 19 1991 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 560 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991 |
---|---|

Country/Territory | India |

City | New Delhi |

Period | 12/17/91 → 12/19/91 |

### Bibliographical note

Publisher Copyright:© Springer-Verlag Berlin Heidelberg 1991.

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science