AbstractBerman 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
- Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, and Steven Rudich. Reducing the complexity of reductions. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 730-738, El Paso, Texas, 4-6 May 1997.
- Manindra Agrawal, Eric Allender, and Steven Rudich. Reductions in circuit complexity: An isomorphism theorem and a gap theorem. Journal of Computer and System Sciences, 57(2):127-143, October 1998.
- Stephen Fenner, Lance Fortnow, and Stuart A. Kurtz. The isomorphism conjecture holds relative to an oracle. SIAM Journal on Computing, 25(1):193-206, February 1996.
- Ashish V. Naik, John D. Rogers, James S. Royer, and Alan L. Selman. A hierarchy based on output multiplicity. Theoretical Computer Science, 207(1):131-157, 28 October 1998.
Selected references
- Stephen Fenner, Lance Fortnow, and Stuart A. Kurtz. The isomorphism conjecture holds relative to an oracle. In 33rd Annual Symposium on Foundations of Computer Science, pages 30-39, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- Steven A. Fenner, Stuart A. Kurtz, and James S. Royer. Every polynomial-time 1-degree collapses iff P = PSPACE. In 30th Annual Symposium on Foundations of Computer Science, pages 624-629, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.
- Joachim Grollmann and Alan L. Selman. Complexity measures for public-key cryptosystems (preliminary report). In 25th Annual Symposium on Foundations of Computer Science, pages 495-503, Singer Island, Florida, 24-26 October 1984. IEEE.
- Stuart A. Kurtz. On the random oracle hypothesis. Information and Control, 57(1):40-47, April 1983.
- Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859-868, October 1992.
- Charles Rackoff. Relativized questions involving probabilistic algorithms. Journal of the ACM, 29(1):261-268, January 1982.