Isomorphism conjecture fails relative to a random oracle

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

36 Scopus citations

Abstract

L. Berman and J. Hartmanis conjectured that there is a polynomial-time computable isomorphism between any two languages m-complete ('Karp' complete) for NP. D. Joseph and P. Young discovered a structurally defined class of NP-complete sets and conjectured that certain of these sets are not isomorphic to the standard NP-complete sets for some one-way functions f. These two conjectures cannot both be correct. We introduce a new family of strong one-way functions, the scrambling functions. If f is a scrambling function, then the above mentioned sets are not isomorphic to the standard NP-complete sets, as Joseph and Young conjectured, and the Berman-Hartmanis conjecture fails. As evidence for the existence of scrambling functions, we show that much more powerful one-way functions, the annihilating functions, exist relative to a random oracle.

Original languageEnglish (US)
Title of host publicationProc Twenty First Annu ACM Symp Theory Comput
PublisherPubl by ACM
Pages157-166
Number of pages10
ISBN (Print)0897913078
StatePublished - Dec 1 1989
EventProceedings of the Twenty First Annual ACM Symposium on Theory of Computing - Seattle, WA, USA
Duration: May 15 1989May 17 1989

Publication series

NameProc Twenty First Annu ACM Symp Theory Comput

Other

OtherProceedings of the Twenty First Annual ACM Symposium on Theory of Computing
CitySeattle, WA, USA
Period5/15/895/17/89

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Isomorphism conjecture fails relative to a random oracle'. Together they form a unique fingerprint.

  • Cite this

    Kurtz, S. A., Mahaney, S. R., & Royer, J. S. (1989). Isomorphism conjecture fails relative to a random oracle. In Proc Twenty First Annu ACM Symp Theory Comput (pp. 157-166). (Proc Twenty First Annu ACM Symp Theory Comput). Publ by ACM.