The isomorphism conjecture fails relative to a random oracle
| Author(s) : | James S. Royer Stephen R. Mahaney Stuart A. Kurtz, |
| Publisher : | N/A |
| Publication Date : | 1989 |
| ISSN : | N/A |
| Abstract : | Berman and Hartmanis [BH77] conjectured that there is a polynomialtime computable isomorphism between any two languages complete for NP with respect to polynomial-time computable many-one (Karp) reductions. Joseph and Young [JY85] gave a structural definition of a class of NP-complete sets---the k-creative sets---and defined a class of sets (the K, |