1989 · 60 citations · 23 references
ComputingComputer ScienceMathematicsAlgorithmsSet TheoryTheory Of ComputationComputability TheoryComputational ComplexityComputational Complexity ClassesStructural ComplexityCompleteness ResultsComplexity-theoretic ReductionsComputational Complexity Of LanguagesNp-complete ProblemsNp-completenessOne-way Functions
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.
23
Algorithmic Information Theory
Gregory J. Chaitin · IBM Journal of Research and Development · 1977 · 1K citations
On Isomorphisms and Density of $NP$ and Other Complete Sets
L. Berman, Juris Hartmanis · SIAM Journal on Computing · 1977 · 460 citations