THE ISOMORPHISM CONJECTURE FAILS RELATIVE TO A RANDOM ORACLE

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.