@inproceedings{f282205f293c4a65b3bf94679a8c6153,

title = "Isomorphism conjecture fails relative to a random oracle",

abstract = "L. Berman and J. Hartmanis conjectured that there is a polynomial-time computable isomorphism between any two languages m-complete ('Karp' complete) for NP. D. Joseph and P. Young discovered a structurally defined class of NP-complete sets and conjectured that certain of these sets are not isomorphic to the standard NP-complete sets for some one-way functions f. These two conjectures cannot both be correct. We introduce a new family of strong one-way functions, the scrambling functions. If f is a scrambling function, then the above mentioned sets are not isomorphic to the standard NP-complete sets, as Joseph and Young conjectured, and the Berman-Hartmanis conjecture fails. As evidence for the existence of scrambling functions, we show that much more powerful one-way functions, the annihilating functions, exist relative to a random oracle.",

author = "Kurtz, {Stuart A.} and Mahaney, {Stephen R.} and Royer, {James S.}",

year = "1989",

language = "English (US)",

isbn = "0897913078",

series = "Proc Twenty First Annu ACM Symp Theory Comput",

publisher = "Publ by ACM",

pages = "157--166",

booktitle = "Proc Twenty First Annu ACM Symp Theory Comput",

note = "Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing ; Conference date: 15-05-1989 Through 17-05-1989",

}