Document Type
Working Paper
Date
1996
Keywords
polynomial-time computable isomorphism, one-way functions, scrambling functions, oracles
Language
English
Disciplines
Computer Sciences
Description/Abstract
Berman and Hartmanis [BH77] conjectured that there is a polynomialtime computable isomorphism between any two languages complete for NP with respect to polynomial-time computable many-one (Karp) reductions. Joseph and Young [JY85] gave a structural definition of a class of NP-complete sets---the k-creative sets---and defined a class of sets (the K k f 's) that are necessarily k-creative. They went on to conjecture that certain of these K k f 's are not isomorphic to the standard NP-complete sets. Clearly, the Berman--Hartmanis and Joseph--Young conjectures cannot both be correct. We introduce a family of strong one-way functions, the scrambling functions. If f is a scrambling function, then K k f is not isomorphic to the standard NP-complete sets, as Joseph and Young conjectured, and the Berman-Hartmanis conjecture fails. Indeed, if scrambling functions exist, then the isomorphism also fails at higher complexity classes such as EXP and NEXP. 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. Random oracles are the first examples of oracles relative to which the isomorphism conjecture fails with respect to higher classes such as EXP and NEXP.
Recommended Citation
Kurtz, Stuart A.; Mahaney, Stephen R.; and Royer, James S., "The Isomorphism Conjecture Fails Relative to a Random Oracle" (1996). Electrical Engineering and Computer Science - All Scholarship. 37.
https://surface.syr.edu/eecs/37
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.
