Ir directamente a la navegación principal Ir directamente a la búsqueda Ir directamente al contenido principal

On the structure and complexity of infinite sets with minimal perfect hash functions

Producción científica: Conference contribution › revisión exhaustiva

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 originalEnglish
Título de la publicación alojadaFoundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings
EditoresSomenath Biswas, Kesav V. Nori
Páginas212-223
Número de páginas12
DOI
EstadoPublished - 1991
Evento11th 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

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen560 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conference

Conference11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991
País/TerritorioIndia
CiudadNew Delhi
Período12/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.

FinanciadoresNúmero del financiador
Hewlett-Packard CorporationCCR-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