Journal of the Association for Computing Machinery, Vol. 42, No. 2, March 1995, pp. 401–420.

The Isomorphism Conjecture Fails Relative to a Random Oracle

STUART A. KURTZ

STEPHEN R. MAHANEY

AND

JAMES S. ROYER

Abstract. 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_{f}^{k}’s) that are necessarily k-creative. They went on to conjecture that certain of these K_{f}^{k}’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_{f}^{k} 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.

Categories and Subject Descriptors. F.m

General Terms. Theory

Additional Key words and Phrases. Isomorphism, conjecture, randomness

Copyright 1995 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.