The isomorphism conjecture fails relative to a random oracle

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Journal of the ACM · 1995 · 58 citations · 25 references

DOIFull text

Open access

Concepts

Abstract

conjectured that there is a polynomial-time computable isomorphism between any two languages complete for NP with respect to polynomial-time computable many-one (Karp) reductions. They went on to conjecture that certain of these K}'s are not isomorphic to the standard NP-complete sets. Clearly, the Berman-Hartmanis and Joseph-Young conjectures cannot both be correct.

References

25