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 = Σ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.
| 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
Funding Information:The authors thank the volunteers who participated in this study. Appreciation is also extended to Josh Apgar (Applied Biomath, LLC) for initial modeling for phase I dose projection, Agnes Costello for helpful discussions during manuscript preparation and for reviewing the manuscript for scientific accuracy, Bill Denney (Human Predictions, LLC) for helpful discussions and analysis of pharmacokinetics/pharmacodynamics during manuscript preparation, Shiyin Foo for contributions in medical monitoring and safety, Jim Jin for statistical input and analysis, Chelsea Toner for clinical operational support, and Jacqueline Wildeman for providing input on pharmacokinetic parameters and biostatistical programming. The authors also thank Lamara D. Shrode, PhD, ISMPP CMPP, of JB Ashtin, who provided editorial support during the preparation of the manuscript. Editorial support was funded by Momenta Pharmaceuticals. This study was sponsored by Momenta Pharmaceuticals (Cambridge, MA). Momenta Pharmaceuticals contributed to the study design, research, data interpretation and the writing, review, and approval of the manuscript.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1991.
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science (all)