TY - GEN
T1 - Isomorphism conjecture fails relative to a random oracle
AU - Kurtz, Stuart A.
AU - Mahaney, Stephen R.
AU - Royer, James S.
PY - 1989
Y1 - 1989
N2 - Summary form only given, as follows. L. Berman and H. Hartmanis (1977) conjectured that there is a polynomial-time computable isomorphism between any two languages m-complete (Karp complete) for NP. D. Joseph and P. Young (1985) discovered a structurally defined class of NP-complete sets and conjectured that certain of these sets (the Kfk's) are not isomorphic to the standard NP-complete sets for some one-way functions f. These two conjectures cannot both be correct. The present authors introduce a new family of strong one-way functions, the scrambling functions. If f is a scrambling function, then Kfk is not isomorphic to the standard NP-complete sets, as Joseph and Young conjectured, and the Berman-Hartmanis conjecture fails. In fact, if scrambling functions exist, then the isomorphism conjecture fails for essentially all natural complexity classes above NP, e.g., PSPACE, EXP, NEXP, and RE. As evidence for the existence of scrambling functions, much more powerful one-way functions--the annihilating functions--are shown to exist relative to a random oracle.
AB - Summary form only given, as follows. L. Berman and H. Hartmanis (1977) conjectured that there is a polynomial-time computable isomorphism between any two languages m-complete (Karp complete) for NP. D. Joseph and P. Young (1985) discovered a structurally defined class of NP-complete sets and conjectured that certain of these sets (the Kfk's) are not isomorphic to the standard NP-complete sets for some one-way functions f. These two conjectures cannot both be correct. The present authors introduce a new family of strong one-way functions, the scrambling functions. If f is a scrambling function, then Kfk is not isomorphic to the standard NP-complete sets, as Joseph and Young conjectured, and the Berman-Hartmanis conjecture fails. In fact, if scrambling functions exist, then the isomorphism conjecture fails for essentially all natural complexity classes above NP, e.g., PSPACE, EXP, NEXP, and RE. As evidence for the existence of scrambling functions, much more powerful one-way functions--the annihilating functions--are shown to exist relative to a random oracle.
UR - http://www.scopus.com/inward/record.url?scp=0024921379&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0024921379&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0024921379
SN - 0818619589
T3 - Proc Struct Complexity Theor Fourth Ann Conf
SP - 2
BT - Proc Struct Complexity Theor Fourth Ann Conf
A2 - Anon, null
PB - IEEE Computer Society
T2 - Proceedings: Structure in Complexity Theory - Fourth Annual Conference
Y2 - 19 June 1989 through 22 June 1989
ER -