Journal of the ACM Bibliography

Stuart A. Kurtz, Stephen R. Mahaney, and James S. Royer. The isomorphism conjecture fails relative to a random oracle. Journal of the ACM, 42(2):401-420, March 1995. [BibTeX entry]

Berman and Hartmanis [1977] conjectured that there is a polynomial-time computable isomorphism between any two languages for NP with respect to polynomial-time computable many-one (Karp) reductions. Joseph and Young [1985] 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 complexity 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.

Berman, L. and Hartmanis, J. 1977. On isomorphism and density of NP and other complete sets. SIAM J. Comput. 6, 305-322.

Joseph, D., and Young, P. 1985. Some remarks on witness functions for nonpolynomial and noncomplete sets in NP. Theoret. Comput. Sci. 29, 225-237. Copyright 1995 by ACM, Inc.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: F.m [Miscellaneous]

General Terms: Theory

Additional Key Words and Phrases: Isomorphism, conjecture, randomness

Selected papers that cite this one

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database