Introduction

Think about a finished Sudoku. Checking whether it's correct takes a few seconds — scan the rows, columns, and boxes. But solving a hard one from scratch can take ages. Checking is easy; finding is hard.

That gap is everywhere. A jigsaw is obvious once assembled. A password is instant to verify but (hopefully) infeasible to guess. A great chess move is easy to appreciate, brutal to discover.

P vs NP asks a startling question: is that gap real, or just a failure of imagination? For every problem whose answers we can check quickly, is there secretly also a way to find them quickly? It is the most important unsolved problem in computer science — and the Clay Mathematics Institute offers one million dollars to whoever settles it.

Easy to Check, Hard to Find

Let's make the gap concrete. Here is a pile of numbers and a target. The task — Subset Sum — is to find some of the numbers that add up exactly to the target.

Checking a proposed answer is trivial: add up the chosen numbers and compare. That's about as many steps as there are numbers. Finding an answer, though, may force you to consider every possible subset — and with n numbers there are 2n2^{n} of them. Add one number and the search space doubles.

Play with it: build a subset by hand (instant feedback — that's checking), then ask the computer to find one by brute force, and slide n upward to watch the effort explode.

<p class="hint">Here is a pile of numbers and a <b>target</b>. Finding a subset that adds up to the target is hard — but <b>checking</b> a proposed answer is trivial. Click numbers to build a subset (that’s checking, and it’s instant). Then ask the computer to <b>find</b> one by brute force, and watch the effort explode as you grow the pile.</p>
<div class="controls">
  <label>Numbers (n): <b id="nval">12</b>
    <input id="n" type="range" min="5" max="90" value="14">
  </label>
  <button id="new" type="button" class="ghost">New pile</button>
</div>
<div class="target">Reach exactly: <b id="target">—</b></div>
<div id="chips" class="chips"></div>
<div class="sumline">Your subset sums to <b id="sum">0</b> <span id="match"></span></div>
<div class="cmp">
  <div class="box ok">
    <div class="lbl">Check an answer</div>
    <div class="big" id="verifySteps">12</div>
    <div class="sub">additions — instant ✓</div>
  </div>
  <div class="box bad">
    <div class="lbl">Find one by brute force</div>
    <div class="big" id="solveSteps">4,096</div>
    <div class="sub" id="solveTime">subsets to try</div>
  </div>
</div>
<div class="bar-btns">
  <button id="solve" type="button">Brute-force solve</button>
</div>
<p id="status" class="status"></p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.controls { display: flex; gap: 1rem; align-items: center; flex-wrap: wrap; margin-bottom: .5rem; }
.controls label { font-size: .9rem; font-weight: 600; display: flex; align-items: center; gap: .5rem; }
input[type=range] { width: 180px; }
.target { font-size: 1.05rem; margin: .3rem 0; }
.target b { font-size: 1.3rem; color: #457b9d; }
.chips { display: flex; flex-wrap: wrap; gap: .4rem; margin: .4rem 0; }
.chip { padding: .35rem .6rem; border: 2px solid #ccc; border-radius: 20px; background: #fff; cursor: pointer; font: 600 14px ui-monospace, monospace; user-select: none; transition: all .1s; }
.chip:hover { border-color: #888; }
.chip.sel { background: #457b9d; color: #fff; border-color: #457b9d; }
.sumline { font-size: .95rem; margin: .3rem 0; }
#match.hit { color: #0a7d33; font-weight: 700; }
#match.miss { color: #888; }
.cmp { display: grid; grid-template-columns: 1fr 1fr; gap: .6rem; margin: .6rem 0; }
.box { border-radius: 10px; padding: .6rem .8rem; text-align: center; }
.box.ok { background: #e7f6ee; border: 1px solid #b6e3c8; }
.box.bad { background: #fdecec; border: 1px solid #f5c2c2; }
.box .lbl { font-size: .82rem; font-weight: 600; color: #555; }
.box .big { font-size: 1.7rem; font-weight: 800; line-height: 1.1; word-break: break-all; }
.box.ok .big { color: #0a7d33; }
.box.bad .big { color: #c0392b; }
.box .sub { font-size: .78rem; color: #666; }
.bar-btns { margin: .3rem 0; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }
.status { font-size: .92rem; font-weight: 600; min-height: 1.3em; margin: .3rem 0 0; line-height: 1.4; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c0392b; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Subset Sum, the heart of the P-vs-NP intuition: CHECKING a proposed subset is ~n additions (fast), but FINDING one means searching up to 2^n subsets.
const nEl = document.getElementById('n');
let nums = [], target = 0;
const selected = new Set();

const fmtInt = x => x.toLocaleString('en-US');

function fmtTime(seconds) {
  if (seconds < 1e-6) return 'under a microsecond';
  const units = [[1, 'seconds'], [60, 'minutes'], [3600, 'hours'], [86400, 'days'], [31557600, 'years']];
  if (seconds < 1) return fmt('%v% milliseconds', { v: (seconds * 1000).toPrecision(2) });
  let label = 'seconds', val = seconds;
  for (const [s, name] of units) { if (seconds >= s) { val = seconds / s; label = name; } }
  if (label === 'years' && val > 1.38e10) return fmt('%v%× the age of the universe', { v: (val / 1.38e10).toPrecision(2) });
  const num = val >= 1000 ? Math.round(val).toLocaleString('en-US') : val.toPrecision(3);
  return `${num} ${label}`;
}

function newPile() {
  const n = Number(nEl.value);
  document.getElementById('nval').textContent = n;
  nums = Array.from({ length: n }, () => 5 + Math.floor(Math.random() * 40));
  // guarantee a solution exists: pick a hidden subset, set target to its sum
  let hidden = nums.filter(() => Math.random() < 0.4);
  if (hidden.length === 0) hidden = [nums[0]];
  target = hidden.reduce((a, b) => a + b, 0);
  selected.clear();
  document.getElementById('target').textContent = target;
  buildChips();
  render();
  updateCompare();
  const st = document.getElementById('status');
  st.className = 'status'; st.textContent = '';
}

function buildChips() {
  const box = document.getElementById('chips');
  box.innerHTML = '';
  nums.forEach((v, i) => {
    const c = document.createElement('button');
    c.className = 'chip'; c.textContent = v; c.dataset.i = i;
    c.addEventListener('click', () => {
      selected.has(i) ? selected.delete(i) : selected.add(i);
      render();
    });
    box.appendChild(c);
  });
}

function render() {
  let sum = 0;
  nums.forEach((v, i) => {
    const sel = selected.has(i);
    document.querySelector(`.chip[data-i="${i}"]`).classList.toggle('sel', sel);
    if (sel) sum += v;
  });
  document.getElementById('sum').textContent = sum;
  const m = document.getElementById('match');
  if (selected.size && sum === target) { m.textContent = '= target ✓'; m.className = 'hit'; }
  else if (selected.size) { m.textContent = fmt('(target is %target%)', { target: target }); m.className = 'miss'; }
  else { m.textContent = ''; m.className = ''; }
}

function updateCompare() {
  const n = nums.length;
  const subsets = Math.pow(2, n);
  document.getElementById('verifySteps').textContent = n;
  document.getElementById('solveSteps').textContent = fmtInt(subsets);
  // assume an optimistic 1 billion subset-checks per second
  document.getElementById('solveTime').textContent = fmt('subsets · ~ %fmtTime%', { fmtTime: fmtTime(subsets / 1e9) });
}

function bruteSolve() {
  const n = nums.length;
  const st = document.getElementById('status');
  const subsets = Math.pow(2, n);
  if (n > 24) {
    st.className = 'status bad';
    st.textContent = fmt('With n = %n%, brute force is %fmtInt% subsets (~%fmtTime% at a billion checks/sec). Skipping the live run so the page stays responsive — but checking any one answer still takes just %n% additions.', { n: n, fmtInt: fmtInt(subsets), fmtTime: fmtTime(subsets / 1e9) });
    return;
  }
  let steps = 0, found = -1;
  for (let mask = 1; mask < subsets; mask++) {
    steps++;
    let s = 0;
    for (let i = 0; i < n; i++) if (mask & (1 << i)) s += nums[i];
    if (s === target) { found = mask; break; }
  }
  selected.clear();
  if (found >= 0) for (let i = 0; i < n; i++) if (found & (1 << i)) selected.add(i);
  render();
  st.className = 'status ' + (found >= 0 ? 'ok' : 'bad');
  st.textContent = found >= 0
    ? fmt('Brute force checked %fmtInt% subsets to find one that hits %target%. Verifying that answer? Just %n% additions.', { fmtInt: fmtInt(steps), target: target, n: n })
    : fmt('No subset hits %target% (checked %fmtInt%).', { target: target, fmtInt: fmtInt(steps) });
  console.log(fmt('n=%n%: brute force %fmtInt% steps; verify %n% steps', { n: n, fmtInt: fmtInt(steps) }));
}

nEl.addEventListener('input', newPile);
document.getElementById('new').addEventListener('click', newPile);
document.getElementById('solve').addEventListener('click', bruteSolve);
newPile();
Result
Console

Notice the asymmetry. The green "check" number grows gently; the red "find" number rockets past billions, then past the age of the universe. NP is the world of problems where checking is easy. P is the world where finding is also easy. P vs NP asks whether those two worlds are actually the same.

P, NP, and NP-complete

Three terms unlock the whole question:

  • P — problems we can solve quickly (in "polynomial time": the work grows like n, n2n^{2}, n3n^{3}… not 2n2^{n}). Sorting a list, finding a shortest route on a map, multiplying numbers.
  • NP — problems whose proposed answers we can check quickly. Subset Sum, Sudoku, and every problem in P all live here (if you can solve fast, you can certainly check fast).
  • NP-complete — the hardest problems in NP. They share a remarkable property: a fast solution to any one of them would give a fast solution to all of NP. Subset Sum, SAT, graph coloring, and the knapsack decision problem are all NP-complete.

That last point is why P vs NP is one question, not thousands. Because the NP-complete problems are all linked by reductions, they rise or fall together. Crack one efficiently and the entire tower falls: P would equal NP.

Why It Matters

This isn't an academic curiosity — the answer would reshape the world.

If P = NP (a fast method exists for the NP-complete problems):

  • Most modern encryption breaks, because its security rests on certain problems being hard to solve but easy to check.
  • Optimization becomes trivial: perfect logistics, drug design, protein folding, scheduling — solved optimally and fast.
  • Mathematics itself changes: finding proofs would become as easy as checking them.

If P ≠ NP (no such method exists — what most researchers believe):

  • The hardness we rely on for security is real and permanent.
  • For thousands of important problems, we must keep settling for approximations and heuristics — exactly the greedy methods you see across this site.

Either answer is a landmark. That's why a single proof is worth a million dollars — and far more in consequence.

Where We Stand

After more than fifty years, P vs NP is still open. In surveys, the large majority of experts bet on P ≠ NP — the gap between checking and finding really is fundamental — but belief is not proof.

Why is it so hard to settle? Several proof strategies have been shown to be inherently incapable of resolving it (results with names like relativization, natural proofs, and algebrization). Each tells us that a successful proof will have to use ideas we don't yet have.

So we live in a strange situation: we build cryptography, plan logistics, and design algorithms as if P ≠ NP, while honestly admitting we cannot yet prove it. The most consequential assumption in computing is, for now, still a conjecture.

Conclusion

Every hard problem on this site — coin change, knapsack, graph coloring — is a face of the same giant question. Each is easy to check and, as far as anyone knows, hard to solve. P vs NP asks whether that "as far as anyone knows" hides a shortcut we've simply never found.

Most of us bet it doesn't — that finding really is harder than checking, that the difficulty is woven into the fabric of computation. But until someone proves it, the gap between an instant check and an impossible search remains the most tantalizing mystery in computer science, and a perfect emblem of the limits of algorithms.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/p-vs-np/Content licensed under CC BY-NC 4.0.