P vs NP

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.

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 $2^{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">{{hint}}</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}} <b id="sum">0</b> <span id="match"></span></div>
<div class="cmp">
  <div class="box ok">
    <div class="lbl">{{check_answer}}</div>
    <div class="big" id="verifySteps">12</div>
    <div class="sub">{{additions_instant}}</div>
  </div>
  <div class="box bad">
    <div class="lbl">{{find_brute}}</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_btn}}</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; }

// Code not found

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.

Three terms unlock the whole question:

• P — problems we can solve quickly (in "polynomial time": the work grows like n, $n^{2}$, $n^{3}$… not $2^{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.

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.

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.

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.