The ismorphism conjecture fails relative to a random oracle
Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer · 1989
Berman and Hartmanis [BH77] conjectured that there is a polynomial-time computable isomorphism between any two languages m-complete (“Karp” complete) for NP. Joseph and Young [JY85] discovered a structurally defined class of NP-complete sets and conjectured that certain of these sets (the Kkƒ's) are not isomorphic to the standard NP-complete sets for some one-way functions ƒ. These two conjectures cannot both be correct.