@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",
}