Introduction

When a problem is NP-hard, textbooks warn you: no efficient algorithm is known that always works. But there is a quiet secret — for many NP-hard problems, almost every random instance is solved almost instantly by even simple algorithms.

Pick a random 3-SAT formula with few clauses relative to variables: a solver finishes in milliseconds. Pick one with many clauses: a quick argument proves it unsatisfiable in milliseconds. It is only near the critical ratio — around 4.27 clauses per variable — that instances become genuinely hard. The rest of the space is easy.

This gap between worst-case and average-case complexity is not a curiosity. It is the foundation of modern cryptography (hard-on-average problems are exactly what encryption needs), and understanding it reshapes how we think about P vs NP. In 1995, Russell Impagliazzo drew the map of all possible worlds, depending on whether average-case hard problems exist.

Try It: The Phase Transition

Random 3-SAT has a sharp phase transition: below ratio ≈ 4.27 clauses/variable almost all instances are satisfiable and easy; above it almost all are unsatisfiable and easy; right at the threshold hardness spikes. Drag the slider to explore.

<div class="controls">
  <label>
    Ratio (clauses / variables): <strong id="ratio-label">4.27</strong>
    <input type="range" id="ratio-slider" min="1" max="8" step="0.05" value="4.27">
  </label>
  <label>
    Variables (n): <strong id="n-label">20</strong>
    <input type="range" id="n-slider" min="8" max="30" step="1" value="20">
  </label>
  <button id="run-btn" type="button">Sample &amp; Solve 20 instances</button>
</div>
<canvas id="chart" width="560" height="200"></canvas>
<div id="stats" class="stats"></div>
<div class="legend">
  <span class="dot sat"></span> SAT (satisfiable)
  <span class="dot unsat"></span> UNSAT (unsatisfiable)
  <span class="bar hard"></span> Backtracks (hardness)
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .8rem; }
label { font-size: .88rem; display: flex; flex-direction: column; gap: .2rem; }
input[type=range] { width: 100%; accent-color: #1d3557; }
button { font: 600 14px system-ui; padding: .45rem 1rem; background: #1d3557;
         color: #fff; border: none; border-radius: 8px; cursor: pointer;
         margin-top: .3rem; align-self: flex-start; }
canvas { width: 100%; max-width: 560px; border: 1px solid #cdd9e3;
         border-radius: 8px; background: #f8fafc; display: block; }
.stats { font-size: .85rem; color: #444; margin: .5rem 0; min-height: 2.8em; }
.legend { font-size: .8rem; color: #555; display: flex; gap: 1.2rem; flex-wrap: wrap; align-items: center; }
.dot { display: inline-block; width: 12px; height: 12px; border-radius: 50%;
       vertical-align: middle; margin-right: 3px; }
.dot.sat { background: #2a9d8f; }
.dot.unsat { background: #e63946; }
.bar { display: inline-block; width: 12px; height: 12px; background: #e9c46a;
       border: 1px solid #c9a820; vertical-align: middle; margin-right: 3px; border-radius: 2px; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// 3-SAT phase-transition demo.
// Generates random 3-SAT instances at a chosen clause/variable ratio,
// solves them with DPLL (unit propagation + backtracking), and counts
// backtracks as a proxy for hardness. The phase transition near ratio 4.27
// is a classical and empirically confirmed result in combinatorics.

const canvas = document.getElementById('chart');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const PAD = { t: 20, r: 20, b: 34, l: 46 };

// --- Random 3-SAT generator ---
// Returns array of clauses; each clause = array of 3 literals.
// A literal is a signed variable index: +v means x_v is true, -v means x_v is false.
function randomSAT(n, m) {
  const clauses = [];
  for (let i = 0; i < m; i++) {
    const vars = [];
    while (vars.length < 3) {
      const v = Math.floor(Math.random() * n) + 1;
      if (!vars.includes(v)) vars.push(v);
    }
    clauses.push(vars.map(v => Math.random() < 0.5 ? v : -v));
  }
  return clauses;
}

// --- DPLL solver with correct unit propagation ---
// assign[v] = 0 (unset), 1 (true), -1 (false) for v = 1..n
function dpll(clauses, n) {
  let backtracks = 0;
  const assign = new Int8Array(n + 1); // 0-indexed slot 0 unused

  // Unit propagation: repeatedly find unit clauses and force their literal.
  // Returns false on conflict (empty clause), true when no more propagation possible.
  function unitProp() {
    let changed = true;
    while (changed) {
      changed = false;
      for (const c of clauses) {
        let unsetLit = null, unsetCount = 0, satisfied = false;
        for (const lit of c) {
          const v = Math.abs(lit), sign = lit > 0 ? 1 : -1;
          if (assign[v] === sign) { satisfied = true; break; } // clause satisfied
          if (assign[v] === 0) { unsetCount++; unsetLit = lit; }
        }
        if (satisfied) continue;
        if (unsetCount === 0) return false;      // all literals false: conflict
        if (unsetCount === 1) {                  // unit clause: force assignment
          assign[Math.abs(unsetLit)] = unsetLit > 0 ? 1 : -1;
          changed = true;
        }
      }
    }
    return true;
  }

  function solve(depth) {
    const snapshot = assign.slice(); // save state before propagation
    if (!unitProp()) { assign.set(snapshot); return false; }

    // Find first unset variable to branch on
    let choice = -1;
    for (let v = 1; v <= n; v++) if (assign[v] === 0) { choice = v; break; }
    if (choice === -1) return true; // all variables assigned, no conflict

    // Branch: try true first
    assign[choice] = 1;
    if (solve(depth + 1)) return true;
    backtracks++;
    assign.set(snapshot); // restore and try false

    assign[choice] = -1;
    if (solve(depth + 1)) return true;
    backtracks++;
    assign.set(snapshot);

    return false; // both branches failed
  }

  const sat = solve(0);
  return { sat, backtracks };
}

let results = [];

function runExperiment() {
  const ratio = parseFloat(document.getElementById('ratio-slider').value);
  const n = parseInt(document.getElementById('n-slider').value);
  const m = Math.round(ratio * n);
  const RUNS = 20;
  results = [];
  let totalBT = 0, satCount = 0;
  for (let i = 0; i < RUNS; i++) {
    const clauses = randomSAT(n, m);
    const { sat, backtracks } = dpll(clauses, n);
    results.push({ sat, backtracks });
    totalBT += backtracks;
    if (sat) satCount++;
  }
  drawChart();
  const avgBT = (totalBT / RUNS).toFixed(1);
  const zone = ratio < 3.0 ? '(easy — almost all SAT)' :
               ratio > 6.0 ? '(easy — almost all UNSAT)' :
               '⚡ near phase transition — hardness spike';
  document.getElementById('stats').innerHTML =
    fmt('<b>n=%n%, m=%m%, ratio=%ratio%</b> &nbsp;|&nbsp; SAT: %satCount%/%RUNS% &nbsp;|&nbsp; Avg backtracks: <b>%avgBT%</b> &nbsp;%zone%', { n: n, m: m, ratio: ratio.toFixed(2), satCount: satCount, RUNS: RUNS, avgBT: avgBT, zone: zone });
  console.log('Ratio:', ratio.toFixed(2), '| n:', n, '| SAT:', satCount + '/' + RUNS,
              '| AvgBacktracks:', avgBT);
}

function drawChart() {
  ctx.clearRect(0, 0, W, H);
  if (!results.length) return;
  const maxBT = Math.max(...results.map(r => r.backtracks), 1);
  const RUNS = results.length;
  const barW = (W - PAD.l - PAD.r) / RUNS;
  const plotH = H - PAD.t - PAD.b;

  // Draw axes
  ctx.strokeStyle = '#adb1b8'; ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(PAD.l, PAD.t); ctx.lineTo(PAD.l, H - PAD.b);
  ctx.lineTo(W - PAD.r, H - PAD.b);
  ctx.stroke();

  // Axis labels
  ctx.fillStyle = '#666'; ctx.font = '11px system-ui';
  ctx.textAlign = 'right';
  ctx.fillText(maxBT, PAD.l - 4, PAD.t + 8);
  ctx.fillText(0, PAD.l - 4, H - PAD.b + 4);
  ctx.textAlign = 'center';
  ctx.fillText('Instance #', PAD.l + (W - PAD.l - PAD.r) / 2, H - 4);
  ctx.save(); ctx.translate(13, PAD.t + plotH / 2); ctx.rotate(-Math.PI / 2);
  ctx.fillText('Backtracks', 0, 0); ctx.restore();

  results.forEach((r, i) => {
    const x = PAD.l + i * barW;
    const bh = maxBT > 0 ? (r.backtracks / maxBT) * plotH : 0;
    // Backtrack bar
    ctx.fillStyle = '#e9c46a';
    ctx.fillRect(x + 2, H - PAD.b - bh, barW - 4, bh);
    // SAT/UNSAT dot below axis
    ctx.fillStyle = r.sat ? '#2a9d8f' : '#e63946';
    ctx.beginPath();
    ctx.arc(x + barW / 2, H - PAD.b + 16, 5, 0, 2 * Math.PI);
    ctx.fill();
  });
}

// Wire controls
document.getElementById('ratio-slider').addEventListener('input', e => {
  document.getElementById('ratio-label').textContent =
    parseFloat(e.target.value).toFixed(2);
});
document.getElementById('n-slider').addEventListener('input', e => {
  document.getElementById('n-label').textContent = e.target.value;
});
document.getElementById('run-btn').addEventListener('click', runExperiment);

// Initial run
runExperiment();
Result
Console

Notice how the solving time and backtrack count peak sharply near ratio 4.27, even though instances on both sides resolve quickly. This is the average-case phenomenon in action: worst-case NP-hardness concentrates near a knife-edge, leaving the vast majority of random instances trivial.

Impagliazzo's Five Worlds

In 1995 Russell Impagliazzo asked: what would life be like depending on the true relationship between worst-case and average-case hardness? He identified five worlds:

  • Algorithmica: P = NP. Every NP problem is efficiently solvable in the worst case, and average-case hardness is a non-issue. Cryptography as we know it is impossible.
  • Heuristica: P ≠ NP, but every NP problem is easy on average (under natural distributions). Hard worst-case instances exist but are vanishingly rare. Secure cryptography is still impossible.
  • Pessiland: Average-case hard problems exist, but none of them can be used to build one-way functions. Hard problems are common, yet cryptography remains out of reach — the most uncomfortable world.
  • Minicrypt: One-way functions exist (so secure symmetric encryption and pseudorandom generators are possible), but public-key cryptography is not. Hard-on-average problems power secret-key systems.
  • Cryptomania: Public-key cryptography exists. Problems hard on average can be used to build trapdoor functions, enabling RSA, Diffie–Hellman, and the internet's security layer.

We believe we live in Cryptomania — but we cannot prove we are not in Heuristica or even Algorithmica. The question of which world is ours is open, and it is one of the deepest unsolved problems in theoretical computer science. It is strictly harder than P vs NP: even if P ≠ NP, we might still live in Heuristica.

Where It Matters

Average-case complexity is not just theory — it determines what is practical and what is secure:

  • Cryptography: every cipher, signature scheme, and key-exchange protocol relies on a problem being hard on random instances. RSA needs factoring to be hard on random numbers; lattice cryptography needs Learning With Errors to be hard on random lattices. Without average-case hardness there is no security.
  • SAT solvers in practice: modern CDCL solvers handle industrial instances with millions of variables because those instances, despite being NP-hard in the worst case, sit far from the phase transition and have exploitable structure.
  • Smoothed analysis: Daniel Spielman and Shang-Hua Teng (2004) explained why the simplex method is fast in practice by analyzing slightly perturbed random inputs — a hybrid of worst-case and average-case thinking.
  • Algorithm engineering: knowing that hard instances cluster near phase transitions lets engineers deliberately avoid those regions in scheduling, planning, and configuration problems.
  • Fine-grained complexity: the average-case analogues of the Exponential Time Hypothesis predict which problems will be hard on typical inputs, guiding the design of heuristics for graph coloring, SAT, and beyond.

Conclusion

Worst-case complexity tells us the sky is the limit for hardness. Average-case complexity asks: how often does that limit actually bite?

For random 3-SAT, hardness concentrates at a razor-thin phase transition and vanishes elsewhere. For cryptography, we need hardness to be widespread — one-way functions must be hard on almost all inputs, not just the worst ones. Whether that need is actually met is the question encoded in Impagliazzo's five worlds, and it remains open.

We build the internet's security on the assumption that we live in Cryptomania. We cannot prove it. Somewhere between the easy random instances and the worst-case intractability of P vs NP lies the true shape of computation — and finding it is one of the great unsolved problems of our time.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/average-case-complexity/Content licensed under CC BY-NC 4.0.