Journal of the ACM · 1995 · 58 citations · 25 references
LawIntellectual Property LawComputational LinguisticsPatent LawPatent LitigationArchetype ReconstructionPigeonhole PrincipleGraph IsomorphismIsomorphism In MathematicsRandom Oracle Model
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.
25
Algebraic methods for interactive proof systems
Carsten Lund, Lance Fortnow, Howard Karloff et al. · Journal of the ACM · 1992 · 702 citations · Full text
On Isomorphisms and Density of $NP$ and Other Complete Sets
L. Berman, Juris Hartmanis · SIAM Journal on Computing · 1977 · 460 citations