The Berman-Hartmanis Conjecture

In 1977, computer scientists Leonard Berman and Juris Hartmanis noticed something striking: every NP-complete problem known at the time could be transformed into every other one not just by a many-one polynomial reduction, but by a bijective polynomial reduction whose inverse is also polynomial. They could be renamed into one another without losing any structure.

From this pattern they made a bold conjecture: all NP-complete sets are polynomially isomorphic — there exists a bijection f computable in polynomial time such that x ∈ A if and only if f(x) ∈ B, and $f^{-1}$ is also polynomial-time. In short, every NP-complete problem is just a relabeling of every other.

This is still open. If true, all the diverse-looking NP-complete problems — SAT, knapsack, graph coloring, scheduling — are the same problem wearing different clothes. If false, the NP-complete class splinters into problems of genuinely different polynomial structure, a crack in the uniformity we assumed.

The conjecture sits in the shadow of P vs NP: if P = NP then everything collapses and the question dissolves; if P ≠ NP the conjecture remains non-trivial and is widely believed to be true but unproven.

The standard reduction from SAT to 3-SAT is not an isomorphism — it is many-to-one. The demo below walks through what an isomorphism would need to preserve: it must be injective (no two inputs map to the same output), surjective (every 3-SAT formula is hit), and both directions must run in polynomial time.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label class="toggle-wrap"><input type="checkbox" id="inj" checked> {{label_inj}}</label>
  <label class="toggle-wrap"><input type="checkbox" id="sur" checked> {{label_sur}}</label>
  <label class="toggle-wrap"><input type="checkbox" id="inv" checked> {{label_inv}}</label>
</div>
<div class="panels">
  <div class="panel" id="sat-panel">
    <div class="panel-title">{{title_sat}}</div>
    <div id="sat-list"></div>
  </div>
  <div class="arrow-col" id="arrow-col"></div>
  <div class="panel" id="tsat-panel">
    <div class="panel-title">{{title_tsat}}</div>
    <div id="tsat-list"></div>
  </div>
</div>
<div class="status" id="status"></div>
<div class="legend">
  <span class="dot ok"></span>{{legend_ok}} &nbsp;
  <span class="dot bad"></span>{{legend_bad}}
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #1a1a2e; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; flex-direction: column; gap: .35rem; margin-bottom: .9rem; }
.toggle-wrap { display: flex; align-items: center; gap: .5rem; cursor: pointer; font-size: .88rem; }
.toggle-wrap input { width: 16px; height: 16px; cursor: pointer; accent-color: #1d3557; }
.panels { display: flex; align-items: flex-start; gap: 0; }
.panel { flex: 1; border: 1.5px solid #cdd9e3; border-radius: 8px; overflow: hidden; min-width: 0; }
.panel-title { background: #1d3557; color: #fff; font-weight: 700; font-size: .82rem;
               padding: .4rem .7rem; letter-spacing: .02em; }
.formula { padding: .38rem .7rem; font-family: ui-monospace, monospace; font-size: .82rem;
           border-bottom: 1px solid #e4eaf0; transition: background .2s; cursor: default; }
.formula:last-child { border-bottom: none; }
.formula.highlight { background: #dff0e8; }
.formula.collision { background: #fde8e8; }
.formula.unreachable { opacity: .38; }
.arrow-col { display: flex; flex-direction: column; align-items: center; justify-content: flex-start;
             min-width: 60px; padding-top: 2.2rem; gap: 0; }
.arrow { font-size: .75rem; color: #1d3557; font-weight: 600; text-align: center;
         height: 32px; display: flex; align-items: center; justify-content: center;
         transition: color .2s; white-space: nowrap; }
.arrow.bad { color: #c92f3c; }
.arrow.ok { color: #0a7d33; }
.status { margin: .65rem 0 .3rem; font-weight: 700; font-size: .93rem; min-height: 1.3em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.legend { font-size: .78rem; color: #555; display: flex; align-items: center; gap: .3rem; flex-wrap: wrap; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; }
.dot.ok { background: #0a7d33; }
.dot.bad { background: #c92f3c; }

// Code not found

Toggle each property and see which formulas survive. The key insight: a p-isomorphism cannot just pad arbitrarily — the padding must be recoverable (invertible) in polynomial time. That recoverability requirement is what makes building and verifying isomorphisms so delicate.

Status: open — conjectured by Berman and Hartmanis in 1977, still unresolved.

The conjecture has a tight web of connections to other open problems:

• Sparse NP-complete sets: Mahaney's theorem (1982) proved that if a sparse set (one with only polynomially many strings of each length) is NP-complete under many-one reductions, then P = NP. Berman and Hartmanis observed that two isomorphic sets must have the same density — so if any NP-complete set is sparse, the conjecture is false (since SAT is dense). Mahaney's theorem then kicks in and implies P = NP. This chain links isomorphism to the deepest open question in complexity.
• Paddability: most known NP-complete problems are paddable — you can append a harmless suffix to an instance without changing its answer. Paddable problems are all p-isomorphic to each other, which is why the conjecture held for every example Berman and Hartmanis checked.
• Polynomial-time computable bijections: building a bijection whose inverse is also polynomial is far harder than just building a many-one reduction. This is the structural gap that keeps the conjecture open.
• Counterexamples? No non-isomorphic pair of NP-complete sets has ever been found. But absence of counterexample is not a proof.

The Berman-Hartmanis conjecture is one of the cleanest structural questions about P vs NP: not "is NP hard?" but "is NP uniform?" — and we do not know.

An abstract question about bijections turns out to have real consequences:

• Cryptographic hardness: if all NP-complete problems are isomorphic, then hardness assumptions based on which NP-complete problem you use are structurally equivalent — they differ only in the encoding. Cryptographers care about this when arguing that breaking their scheme is "as hard as SAT."
• Theory of reductions: the conjecture draws a line between many-one reductions (which can collapse structure) and isomorphisms (which preserve it). Understanding that line matters for knowing what properties survive a reduction.
• Density and counting: isomorphic sets have the same density profile. Mahaney's theorem turned that observation into a powerful tool: sparseness of NP-complete sets would break isomorphism and imply P = NP.
• Teaching structural complexity: the conjecture is the clearest example of asking not "is problem A hard?" but "do hard problems form a single club or many clubs?" — a distinction that runs through all of structural complexity theory.

Whether true or false, the Berman-Hartmanis conjecture sharpens our picture of what NP-completeness really means, beyond the mere fact that problems reduce to each other.

Berman and Hartmanis asked a deceptively simple question: if every NP-complete problem reduces to every other, are they all really the same problem? Their conjecture — that yes, they are all polynomially isomorphic — has survived nearly fifty years without a proof or a counterexample.

It sits at the intersection of P vs NP, the theory of reductions, and the density of hard sets. Settle it and you have said something profound about the internal architecture of computational hardness. For now, all the NP-complete problems we know look like they could be the same thing — we just haven't been able to write down the renaming that proves it.