Resumen
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 = ΣE2 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.
| Idioma original | English |
|---|---|
| Título de la publicación alojada | Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings |
| Editores | Somenath Biswas, Kesav V. Nori |
| Páginas | 212-223 |
| Número de páginas | 12 |
| DOI | |
| Estado | Published - 1991 |
| Evento | 11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991 - New Delhi, India Duración: dic 17 1991 → dic 19 1991 |
Serie de la publicación
| Nombre | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volumen | 560 LNCS |
| ISSN (versión impresa) | 0302-9743 |
| ISSN (versión digital) | 1611-3349 |
Conference
| Conference | 11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991 |
|---|---|
| País/Territorio | India |
| Ciudad | New Delhi |
| Período | 12/17/91 → 12/19/91 |
Nota bibliográfica
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 1991.
Financiación
*A full version is available from the authors. tDept of Computer Science, University of Manitoba, Winnipeg, Manitoba R3T 2N2, Canada. Work done in part while at Dartmouth College. Research supported by the National Science Foundation under grant RII-9003056. tDepartment of Computer Science, University of Rochester, l~ochester, NY 14627. Research supported in part by a Hewlett-Packard Corporation equipment grant and by the National Science Foundation under grant CCR-8809174/CCR-8996198 and a Presidential Young Investigator Award. w of Computer Sciences, University of Wisconsin, Madison, WI 53706. Research supported in part by the National Science Foundation under grant DMS-8501521.
| Financiadores | Número del financiador |
|---|---|
| Hewlett-Packard Corporation | CCR-8809174/CCR-8996198, DMS-8501521 |
| National Science Foundation (NSF) | RII-9003056 |
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science
Huella
Profundice en los temas de investigación de 'On the structure and complexity of infinite sets with minimal perfect hash functions'. En conjunto forman una huella única.Citar esto
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver