%%% ====================================================================
%%% @LaTeX-file{
%%% filename = "kurtzmr95.ltx",
%%% date = "20 November 1995",
%%% time = "21:41:32 EST",
%%% author = "David M. Jones",
%%% email = "jacm@theory.lcs.mit.edu",
%%% url = "http://theory.lcs.mit.edu/~jacm/",
%%% address = "Journal of the ACM
%%% MIT Laboratory for Computer Science
%%% Room NE43-316
%%% 545 Technology Square
%%% Cambridge, MA 02139
%%% USA",
%%% telephone = "(617) 253-5936",
%%% FAX = "(617) 253-3480",
%%% checksum = "59045 114 530 4312",
%%% codetable = "ISO/ASCII",
%%% supported = "yes",
%%% docstring = "Copyright (c) 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.
%%%
%%% This is a LaTeX2e file. To process it, you will
%%% need a copy of the acmabs document class, which is
%%% available via the following URL:
%%%
%%% http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%% ",
%%% }
%%% ====================================================================
\documentclass{acmabs}
\begin{document}
\Journal{Journal of the ACM}
\refkey{KurtzMR95}
\title{The Isomorphism Conjecture Fails Relative to a Random Oracle}
\author{Stuart~A. Kurtz \and Stephen~R. Mahaney \and James~S. Royer}
\Pages{401--420}
\Month{March}
\Year{1995}
\Volume{42}
\Number{2}
\maketitle
\begin{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^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. \par We
introduce a family of strong one-way functions, the {\em 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 {\em annihilating\/}
functions---exist relative to a random oracle. \par 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. \par Berman, L. and
Hartmanis, J. 1977. On isomorphism and density of NP and other complete sets.
{\em SIAM J.\ Comput.\ 6}, 305--322. \par Joseph, D., and Young, P. 1985.
Some remarks on witness functions for nonpolynomial and noncomplete sets in
NP. {\em Theoret.\ Comput.\ Sci.\ 29}, 225--237.
\end{abstract}
\begin{categories}
F.m
\end{categories}
\begin{terms}
Theory
\end{terms}
\begin{keywords}
Isomorphism, conjecture, randomness
\end{keywords}
\end{document}