Sa. Kurtz et al., THE ISOMORPHISM CONJECTURE FAILS RELATIVE TO A RANDOM ORACLE, Journal of the Association for Computing Machinery, 42(2), 1995, pp. 401-420
Berman and Hartmanis [1977] conjectured that there is a polynomial-tim
e computable isomorphism between any two languages complete for NP wit
h respect to polynomial-time computable many-one (Karp) reductions. Jo
seph and Young [1985] gave a structural definition of a class of NP-co
mplete sets-the k-creative sets-and defined a class of sets (the K(f)k
,s) that are necessarily k-creative. They went on to conjecture that c
ertain of these K(f)k,s are not isomorphic to the standard NP-complete
sets. Clearly, the Berman-Hartmains and Joseph-Young conjectures cann
ot both be correct. We introduce a family of strong one-way functions,
the scrambling functions. If f is a scrambling function, then K(f)k i
s not isomorphic to the standard NP-complete sets, as Joseph and Young
conjectured, and the Berman-Hartmanis conjecture fails. Indeed, if sc
rambling functions exist, then the isomorphism also fails at higher co
mplexity classes such as EXP and NEXP. As evidence for the existence o
f scrambling functions, we show that much more powerful one-way functi
ons-the annihilating functions-exist relative to a random oracle. Rand
om oracles are the first examples of oracles relative to which the iso
morphism conjecture fails with respect to higher classes such as EXP a
nd NEXP.