Berman-Hartmanis Isomorphism Conjecture

Berman-Hartmanis Isomorphism Conjecture

Definitions and mathematical statement

A language $A\subseteq\{0,1\}^*$ is NP-complete under polynomial-time many-one reductions if $A\in\mathrm{NP}$ and every NP language $L$ has a polynomial-time map $f$ with $x\in L\iff f(x)\in A$. A polynomial-time isomorphism between $A$ and $B$ is a bijection $h:\{0,1\}^*\to\{0,1\}^*$ satisfying \[ x\in A\iff h(x)\in B, \qquad h,h^{-1}\text{ polynomial-time computable}. \] The conjecture asserts such an $h$ for every pair of NP-complete languages. Reductions in both directions alone do not supply a bijection or an efficiently computable inverse.

Formulation and concept references: [S1].

Short English statement

Are all NP-complete languages the same up to a reversible, polynomial-time change of their binary encodings?

Research attempt

Current frontier.

The Hartmanis problem survey discusses the isomorphism conjecture, padding, scrambling, and restricted reductions separately [S1], Sections 5.1--5.3. In particular, results for completeness under weaker reduction notions do not establish the statement for all polynomial-time many-one complete sets. Its discussion also records relativized obstacles. The present attempt isolates a sufficient effective Cantor--Bernstein mechanism and checks exactly which features arbitrary Karp reductions lack. It does not assume that injectivity supplies efficient inversion.

Attack route.

One route tries to pad every complete language reversibly; another tries to convert reductions in both directions directly into a bijection. A purely set-theoretic Cantor--Bernstein theorem ignores the cost of recognizing the components used in its proof. We pursue a version in which that recognition is forced to terminate quickly by a decreasing integer measure: string length. The remaining task is then an explicit upgrade theorem for reductions, rather than an unspecified "back-and-forth" construction.

Attempt: effective Cantor--Bernstein under explicit hypotheses.

Let $A,B\subseteq\{0,1\}^*$. Suppose there are injections $f,g$ with \[ x\in A\iff f(x)\in B,\qquad y\in B\iff g(y)\in A. \] Assume $f,g$ are polynomial-time computable, satisfy \begin{equation}\label{wsref-0-65-71-31-37-35-2d-6c-65-6e-67-74-68} |f(x)|>|x|,\qquad |g(y)|>|y|, \end{equation} and have polynomial-time partial inverses: given a string, an algorithm recognizes membership in the range and either returns the unique preimage or reports that none exists. Then $A$ and $B$ are polynomial-time isomorphic in the exact sense of the question.

Proof. Make two disjoint copies $X,Y$ of the set of binary strings. Draw an edge from $x\in X$ to $f(x)\in Y$ and from $y\in Y$ to $g(y)\in X$. Every vertex has exactly one outgoing edge and at most one incoming edge. By (eq175-length), following edges backwards strictly decreases string length, so every component has a unique initial vertex, called its root. There are no cycles or doubly infinite chains. Each component is a one-sided alternating ray starting in $X$ or in $Y$.

The root side of a vertex is polynomial-time decidable. Alternate the range tests for $f$ and $g$ as appropriate; each successful inversion shortens the string by at least one. There are at most the original length plus one tests, each on strings no longer than the original. Stop at the first failed range test. Polynomial running time follows with a fixed polynomial depending on the two given inverse algorithms.

Define \begin{equation}\label{wsref-0-65-71-31-37-35-2d-68} h(x)=\begin{cases} f(x),&\text{the root of its component is in }X,\\ g^{-1}(x),&\text{the root is in }Y. \end{cases} \end{equation} In the second case every $X$-vertex has a predecessor in $Y$, so the inverse is defined. On a ray rooted in $X$, this matches successive $X$-vertices with their $f$-successors. On a ray rooted in $Y$, it matches each $X$-vertex with its $g$-predecessor. In either case it is a bijection between the two sets of vertices of the ray. The inverse is $f^{-1}(y)$ on an $X$-rooted ray and $g(y)$ on a $Y$-rooted ray. Both maps are polynomial-time by the root algorithm and the given maps. All their paired edges preserve the relevant membership condition, proving $h(A)=B$. This proves the lemma. $\square$

The output length is also controlled: it is either the output of one polynomial-time map or a shorter predecessor. No infinite component search or hidden oracle has been used.

Attempt: what padding would have to supply.

The lemma would prove the full conjecture if every pair of NP-complete languages admitted mutual reductions satisfying its three extra properties: injectivity, effective range inversion, and strict length increase. The existence of ordinary many-one reductions gives none of those properties for free. Two different inputs may have the same image, and their membership labels alone provide no reversible encoding of the discarded information.

For a paddable target, one might try to replace a reduction $r(x)$ by an encoding $\operatorname{pad}(r(x),x)$. This works only if padding preserves membership and the pair can be decoded efficiently from the target language's own strings. It is not enough to form the pair in an external cylinder language and then apply another arbitrary reduction: that last reduction may destroy the very injectivity and decoding that were gained. The role of paddability and scrambling in this obstruction is discussed in [S1], Sections 5.1--5.2.

Likewise, an injection can be difficult to invert on its range. In that case the predecessor tests in the proof are not algorithms of known polynomial complexity. If length increase is dropped, backwards paths may not terminate, and even a finite component can contain a cycle. An effective treatment of those components might still be possible in special cases, but it requires a new argument; the proof above does not cover them.

As a mechanical test of the pairing construction, take $f(x)=0x$ and $g(y)=1y$. Range inversion deletes the appropriate leading bit. The accompanying script constructs (eq175-h) and its inverse and checks both compositions on all strings up to a specified finite length. The all-string proof remains the ray argument, not this finite test. These prefix maps test the combinatorics, not arbitrary NP-complete languages.

Attempt: a dependency warning proved directly.

An affirmative answer to the full question would imply $\mathrm P\ne\mathrm{NP}$. Suppose instead that $\mathrm P=\mathrm{NP}$. Then every nonempty proper language in $\mathrm P$ is NP-complete: given any NP language, decide it in polynomial time and output one fixed yes string or one fixed no string of the target. In particular \[ A=\{0\},\qquad B=\{0x:x\in\{0,1\}^*\} \] would both be NP-complete. But no bijection of all strings can carry the singleton $A$ onto the infinite set $B$. Thus the universal isomorphism assertion fails under $\mathrm P=\mathrm{NP}$.

This uses the exact definition in the question, which does not exclude finite complete languages by an extra convention. It confirms the warning in [S1]. A theorem upgrading all complete sets to the reversible embeddings above is therefore not a modest coding exercise: it would already imply a major complexity separation. Conversely, a failure to upgrade a particular chosen pair of reductions would not disprove the conjecture, which permits entirely different isomorphisms.

Stress test.

The bijection acts on all binary strings, including the empty string, and not just on the yes instances. Roots of length zero cause no problem: no shorter predecessor can exist. Membership equivalences are used in both directions along each edge, so the inverse also preserves the no instances. Fixed polynomials bound the running times for all inputs; nonuniform inverse circuits are not substituted for uniform algorithms.

Set-theoretic reducibility and polynomial-time invertibility remain distinct. The source's oracle and scrambling discussions prevent treating this proof as a general relativizing solution. No one-way function is assumed to exist, and no unproved cryptographic hypothesis is smuggled into the status of the upgrade step.

Outcome.

Outcome: Conditional reduction.

The attempt gives a complete constructive proof of an efficient Cantor--Bernstein lemma with explicit length and inversion conditions. The missing input is a theorem supplying those conditions for arbitrary NP-complete languages. The lemma is an exposition and audit of a standard kind of isomorphism mechanism, not a claim of literature priority. Its application to the universal conjecture remains conditional, and its consequence for $\mathrm P$ versus $\mathrm{NP}$ is explicitly verified.

Sources

• S1 Allender, Cai, Fortnow, Gasarch, Immerman, Kurtz, Royer, and Williams, Open Problems by or Inspired by Juris Hartmanis, ACM SIGACT News 53$4$, 2022, section 5.3, printed p. 7. https://www.cs.umd.edu/~gasarch/open/juris.pdf. Catalogue formulation source.