Berman–Hartmanis conjecture
In structural complexity theory, the Berman–Hartmanis conjecture is an unsolved conjecture named after Leonard C. Berman and Juris Hartmanis that states that all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms. Statement. An isomorphism between formal languages "L" and "L" is a bijective map "f" from strings in the alphabet of "L" to strings in the alphabet of "L", with the property that a string "x" belongs to "L" if and only if "f"("x") belongs to "L". It is a polynomial time isomorphism (or  p-isomorphism for short) if both "f" and its inverse function can be computed in an amount of time polynomial in the lengths of their arguments. Based on these results, Berman and Hartmanis conjectured that all NP-complete languages are "p"-isomorphic. Since "p"-isomorphism preserves paddability, and there exist paddable NP-complete languages, an equivalent way of stating the Berman–Hartmanis conjecture is that all NP-complete languages are paddable. Polynomial time isomorphism is an equivalence relation, and it can be used to partition the formal languages into equivalence classes, so another way of stating the Berman–Hartmanis conjecture is that the  NP-complete languages form a single equivalence class for this relation. Implications. If the Berman–Hartmanis conjecture is true, an immediate consequence would be the nonexistence of sparse NP-complete languages, namely languages in which the number of yes-instances of length "n" grows only polynomially as a function of "n". The known NP-complete languages have a number of yes-instances that grows exponentially, and if "L" is a language with exponentially many yes-instances then it cannot be "p"-isomorphic to a sparse language, because its yes-instances would have to be mapped to strings that are more  than polynomially long in order for the mapping to be one-to-one. The nonexistence of sparse NP-complete languages in turn implies that P ≠ NP, because if P = NP then every nontrivial language in P (including some sparse ones, such as the language of binary strings all of whose bits are zero) would be NP-complete. In 1982, Steve Mahaney published his proof that the nonexistence of sparse NP-complete languages (with NP-completeness defined in the standard way using many-one reductions) is in fact equivalent to the statement that P ≠ NP; this is Mahaney 's theorem. Even for a relaxed definition of NP-completeness using Turing reductions, the existence of a sparse NP-complete language would imply an unexpected collapse of the polynomial hierarchy. Evidence. As evidence towards the conjecture, showed that an analogous conjecture with a restricted type of reduction is true: every two languages that are complete for NP under AC many-one reductions have an AC isomorphism. And found an oracle machine model in which the analogue to the isomorphism conjecture is true. Evidence against the conjecture was provided by and . Joseph and Young introduced a class of NP-complete problems , the "k"-creative sets, for which no "p"-isomorphism to the standard NP-complete problems is known. Kurtz et al. showed that in oracle machine models given access to a random oracle, the analogue of the conjecture is not true: if "A" is a random oracle, then not all sets complete for NP have isomorphisms in P. Random oracles are commonly used in the theory of cryptography to model cryptographic hash functions that are computationally indistinguishable from random, and the construction of Kurtz et al. can be carried out with such a function in place of the oracle. For this reason, among  others, the Berman–Hartmanis isomorphism conjecture is believed false by many complexity theorists.