Introduction

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−1f^{-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.

Try It: Building a Polynomial Isomorphism

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">A polynomial isomorphism between two NP-complete problems must be <b>injective</b> (no collisions), <b>surjective</b> (every output is reachable), and <b>invertible in poly-time</b>. Toggle each requirement to see what happens when one is dropped.</p>
<div class="controls">
  <label class="toggle-wrap"><input type="checkbox" id="inj" checked> Injective (no two inputs → same output)</label>
  <label class="toggle-wrap"><input type="checkbox" id="sur" checked> Surjective (every 3-SAT formula is reachable)</label>
  <label class="toggle-wrap"><input type="checkbox" id="inv" checked> Invertible in polynomial time</label>
</div>
<div class="panels">
  <div class="panel" id="sat-panel">
    <div class="panel-title">SAT formulas (domain)</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">3-SAT formulas (codomain)</div>
    <div id="tsat-list"></div>
  </div>
</div>
<div class="status" id="status"></div>
<div class="legend">
  <span class="dot ok"></span>isomorphism property holds &nbsp;
  <span class="dot bad"></span>property violated
</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; }

// We work with 4 small SAT formulas and 4 small 3-SAT formulas.
// A "polynomial isomorphism" f: SAT -> 3SAT must be:
//   injective  : f is one-to-one (no two SAT formulas map to the same 3-SAT formula)
//   surjective : f is onto (every 3-SAT formula is the image of some SAT formula)
//   invertible : f^{-1} is also poly-time (here we just flag if a fake non-invertible
//   padding is in use)
//
// The demo has one "base" bijective mapping and lets the user break each property independently to see what goes wrong.

const SAT_FORMULAS = [
  '(x₁)',
  '(x₁ ∨ x₂)',
  '(x₁ ∨ x₂) ∧ (¬x₁)',
  '(x₁ ∨ x₂ ∨ x₃) ∧ (¬x₂)',
];
const TSAT_FORMULAS = [
  '(x₁ ∨ x₁ ∨ x₁)',
  '(x₁ ∨ x₂ ∨ x₂)',
  '(x₁ ∨ x₂ ∨ x₂) ∧ (¬x₁ ∨ ¬x₁ ∨ ¬x₁)',
  '(x₁ ∨ x₂ ∨ x₃) ∧ (¬x₂ ∨ ¬x₂ ∨ ¬x₂)',
];
// Base bijection: index i in SAT maps to index i in TSAT (a true isomorphism)
const BASE_MAP = [0, 1, 2, 3];

function buildMapping(injective, surjective, invertible) {
  // Start from the base bijection and deliberately break selected properties.
  // Break injectivity: map index 1 and 2 both to TSAT index 1 (collision).
  // Break surjectivity: index 3 in TSAT is never the image of any SAT formula.
  // Break invertibility: add an unrecoverable padding note (cosmetic here).
  let map = BASE_MAP.slice(); // copy

  if (!injective) {
    // map SAT[1] and SAT[2] both to TSAT[1]
    map[1] = 1;
    map[2] = 1; // collision
  }
  if (!surjective) {
    // skip TSAT[3]: redirect SAT[3] to TSAT[0] instead
    map[3] = 0;
  }
  return map;
}

function render() {
  const inj = document.getElementById('inj').checked;
  const sur = document.getElementById('sur').checked;
  const inv = document.getElementById('inv').checked;
  const mapping = buildMapping(inj, sur, inv);

  // Which TSAT indices are hit?
  const hitSet = new Set(mapping);
  // Which TSAT indices are hit more than once?
  const counts = [0,0,0,0];
  mapping.forEach(t => counts[t]++);

  // Render SAT list
  const satList = document.getElementById('sat-list');
  satList.innerHTML = '';
  SAT_FORMULAS.forEach((f, i) => {
    const div = document.createElement('div');
    div.className = 'formula';
    div.textContent = f;
    satList.appendChild(div);
  });

  // Render arrows
  const arrowCol = document.getElementById('arrow-col');
  arrowCol.innerHTML = '';
  mapping.forEach((t, i) => {
    const div = document.createElement('div');
    const isCollision = counts[t] > 1;
    div.className = 'arrow' + (isCollision ? ' bad' : ' ok');
    div.textContent = '→ ' + (t + 1);
    arrowCol.appendChild(div);
  });

  // Render TSAT list
  const tsatList = document.getElementById('tsat-list');
  tsatList.innerHTML = '';
  TSAT_FORMULAS.forEach((f, i) => {
    const div = document.createElement('div');
    let cls = 'formula';
    if (hitSet.has(i)) {
      cls += counts[i] > 1 ? ' collision' : ' highlight';
    } else {
      cls += ' unreachable';
    }
    div.className = cls;
    div.textContent = f;
    tsatList.appendChild(div);
  });

  // Determine overall status
  const hasCollision = mapping.some((t, i) => mapping.indexOf(t) !== i);
  const missingTarget = [0,1,2,3].some(t => !hitSet.has(t));
  const notInv = !inv;

  const problems = [];
  if (!inj || hasCollision) problems.push('NOT injective (collision)');
  if (!sur || missingTarget) problems.push('NOT surjective (unreachable formula)');
  if (notInv) problems.push('NOT invertible in poly-time');

  const statusEl = document.getElementById('status');
  if (problems.length === 0) {
    statusEl.textContent = '✓ Valid polynomial isomorphism: bijective + invertible';
    statusEl.className = 'status ok';
  } else {
    statusEl.textContent = '✗ ' + problems.join(' · ');
    statusEl.className = 'status bad';
  }

  // Log verification to console
  console.log('Mapping:', mapping, '| Injective:', inj && !hasCollision, '| Surjective:', sur && !missingTarget, '| Invertible:', inv);
}

document.getElementById('inj').addEventListener('change', render);
document.getElementById('sur').addEventListener('change', render);
document.getElementById('inv').addEventListener('change', render);
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/berman-hartmanis/Content licensed under CC BY-NC 4.0.