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

Abstract

Summary form only given, as follows. L. Berman and H. Hartmanis (1977) conjectured that there is a polynomial-time computable isomorphism between any two languages m-complete (Karp complete) for NP. D. Joseph and P. Young (1985) discovered a structurally defined class of NP-complete sets and conjectured that certain of these sets (the Kfk's) are not isomorphic to the standard NP-complete sets for some one-way functions f. These two conjectures cannot both be correct. The present authors introduce a new family of strong one-way functions, the scrambling functions. If f is a scrambling function, then Kfk is not isomorphic to the standard NP-complete sets, as Joseph and Young conjectured, and the Berman-Hartmanis conjecture fails. In fact, if scrambling functions exist, then the isomorphism conjecture fails for essentially all natural complexity classes above NP, e.g., PSPACE, EXP, NEXP, and RE. As evidence for the existence of scrambling functions, much more powerful one-way functions--the annihilating functions--are shown to exist relative to a random oracle.

Original languageEnglish (US)
Title of host publicationProc Struct Complexity Theor Fourth Ann Conf
Editors Anon
PublisherIEEE Computer Society
Number of pages1
ISBN (Print)0818619589
StatePublished - Dec 1 1989
EventProceedings: Structure in Complexity Theory - Fourth Annual Conference - Eugene, OR, USA
Duration: Jun 19 1989Jun 22 1989

Publication series

NameProc Struct Complexity Theor Fourth Ann Conf

Other

OtherProceedings: Structure in Complexity Theory - Fourth Annual Conference
CityEugene, OR, USA
Period6/19/896/22/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 Anon (Ed.), Proc Struct Complexity Theor Fourth Ann Conf (Proc Struct Complexity Theor Fourth Ann Conf). IEEE Computer Society.