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/12/1

Y1 - 1989/12/1

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

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 -