Math Conjectures

Berman–Hartmanis Isomorphism Conjecture

OPENMajorConjectureProposed 1977 · Standard version

Canonical statement

If A,B⊆{0,1}∗A,B\subseteq\{0,1\}^* are both NPNP-complete, where NPNP is nondeterministic polynomial time, and completeness is under polynomial-time many-one reductions, then there exists a bijection f:{0,1}∗→{0,1}∗f:\{0,1\}^*\to\{0,1\}^* such that ff and f−1f^{-1} are polynomial-time computable and
x∈A  ⟺  f(x)∈B. x\in A\iff f(x)\in B.
View source LaTeX
If \(A,B\subseteq\{0,1\}^*\) are both \(NP\)-complete,
where \(NP\) is nondeterministic polynomial time, and completeness is
under polynomial-time many-one reductions, then there exists a bijection
\(f:\{0,1\}^*\to\{0,1\}^*\) such that \(f\) and \(f^{-1}\) are
polynomial-time computable and
\[
  x\in A\iff f(x)\in B.
\]
TCS-017:[BermanHartmanis1977][Mahaney1982Sparse][AroraBarak2009]
Theoretical computer scienceLogic and foundations

Notes

The isomorphism conjecture of Berman and Hartmanis (1977) predicts that all NPNP-complete sets are polynomially isomorphic: for any two sets complete for NPNP under polynomial-time many-one reductions there is a bijection of {0,1}∗\{0,1\}^*, computable and invertible in polynomial time, mapping one onto the other [BermanHartmanis1977]. The conjecture would make NPNP-completeness structurally rigid, in analogy with the isomorphism of complete sets in computability theory.

Berman and Hartmanis showed that paddable sets are p-isomorphic, and since all standard natural NPNP-complete sets are paddable, they are pairwise p-isomorphic [BermanHartmanis1977]. The conjecture implies that no sparse set can be NPNP-complete, and Mahaney's theorem, that sparse NPNP-complete sets exist only if P=NPP=NP, resolved a related conjecture from the same paper [Mahaney1982Sparse]. Textbook accounts appear in Arora and Barak [AroraBarak2009].

Artificially constructed complete sets resist all known isomorphism techniques, yet no counterexample has been found. Since the conjecture implies P≠NPP\neq NP, a proof is currently out of reach, and the question remains open in both directions.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.