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

Judy Goldsmith; Lane A. Hemachandra; Kenneth Kunen

doi:10.1007/3-540-54967-6_70

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

Judy Goldsmith
, Lane A. Hemachandra
, Kenneth Kunen

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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₂ 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	https://doi.org/10.1007/3-540-54967-6_70
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.

Funding

*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.

Funders	Funder number
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

Access to Document

10.1007/3-540-54967-6_70

Cite this

Goldsmith, J., Hemachandra, L. A., & Kunen, K. (1991). On the structure and complexity of infinite sets with minimal perfect hash functions. In S. Biswas, & K. V. Nori (Eds.), Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings (pp. 212-223). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 560 LNCS). https://doi.org/10.1007/3-540-54967-6_70

Goldsmith, Judy ; Hemachandra, Lane A. ; Kunen, Kenneth. / On the structure and complexity of infinite sets with minimal perfect hash functions. Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings. editor / Somenath Biswas ; Kesav V. Nori. 1991. pp. 212-223 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{722e34767dd349a2b1cf2abd20103b2e,

title = "On the structure and complexity of infinite sets with minimal perfect hash functions",

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.",

author = "Judy Goldsmith and Hemachandra, \{Lane A.\} and Kenneth Kunen",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1991.; 11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991 ; Conference date: 17-12-1991 Through 19-12-1991",

year = "1991",

doi = "10.1007/3-540-54967-6\_70",

language = "English",

isbn = "9783540549673",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "212--223",

editor = "Somenath Biswas and Nori, \{Kesav V.\}",

booktitle = "Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings",

}

Goldsmith, J, Hemachandra, LA & Kunen, K 1991, On the structure and complexity of infinite sets with minimal perfect hash functions. in S Biswas & KV Nori (eds), Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 560 LNCS, pp. 212-223, 11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991, New Delhi, India, 12/17/91. https://doi.org/10.1007/3-540-54967-6_70

On the structure and complexity of infinite sets with minimal perfect hash functions. / Goldsmith, Judy; Hemachandra, Lane A.; Kunen, Kenneth.
Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings. ed. / Somenath Biswas; Kesav V. Nori. 1991. p. 212-223 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 560 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Goldsmith, Judy

AU - Hemachandra, Lane A.

AU - Kunen, Kenneth

PY - 1991

Y1 - 1991

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85030636927

UR - https://www.scopus.com/pages/publications/85030636927#tab=citedBy

U2 - 10.1007/3-540-54967-6_70

DO - 10.1007/3-540-54967-6_70

M3 - Conference contribution

AN - SCOPUS:85030636927

SN - 9783540549673

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

SP - 212

EP - 223

BT - Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings

A2 - Biswas, Somenath

A2 - Nori, Kesav V.

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

Y2 - 17 December 1991 through 19 December 1991

ER -

Goldsmith J, Hemachandra LA, Kunen K. On the structure and complexity of infinite sets with minimal perfect hash functions. In Biswas S, Nori KV, editors, Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings. 1991. p. 212-223. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-54967-6_70

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

Abstract

Publication series

Conference

Bibliographical note

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this