Topic · Computation

P vs NP

The biggest open question in computer science.

Some problems are easy to solve. Others are easy to check once somebody hands you the answer. P vs NP asks whether those two classes are secretly the same — and a yes would shatter modern cryptography. The Explorer is a small 3-SAT solver that lets you watch why verification is trivial but search is brutal: drop in a formula, then follow DPLL down the backtracking tree as it tries assignments and prunes whole branches with a single contradiction.

Discover the story → Open the Explorer

Step one · Two classes of problems

Solvable quickly vs verifiable quickly

P is the class of decision problems a deterministic machine can solve in polynomial time — multiply two numbers, sort a list, check whether a graph is connected. NP is the class where, given a candidate solution, a polynomial-time machine can verify the answer is correct. The two are not obviously the same. Sudoku is the textbook example: filling in a 9×9 grid is genuinely hard, but if a friend hands you a completed grid you can confirm every row, column and box in a single linear sweep. The hard part is finding the solution; the easy part is checking it.

Step two · NP-completeness

Cook 1971, Karp 1972, Levin independently

In 1971 Stephen Cook proved the Cook-Levin theorem: every problem in NP reduces in polynomial time to Boolean satisfiability (SAT). Leonid Levin published the same result independently in the Soviet Union. A year later Richard Karp showed 21 classical problems — 3-SAT, Hamiltonian Path, Clique, Subset Sum, the Travelling Salesman decision version — are all polynomial-time inter-reducible. Today the list runs into thousands: Sudoku N×N, Tetris, generalised Minesweeper, even protein folding lattice models all belong to the same equivalence class. Solve one efficiently and you have solved them all. Cook-Karp-Levin reductions turned a question about one problem into a question about every interesting search problem at once.

Step three · What if P = NP?

Cryptography falls, biology bends, the universe gets boring

A polynomial-time algorithm for 3-SAT would compose with Karp reductions to crack RSA (factoring becomes feasible), break elliptic-curve cryptography, decrypt every TLS session ever recorded, and forge every digital signature. Protein folding would collapse into a polynomial-time look-up. Optimal scheduling, optimal compiler register allocation, optimal route planning — all the NP-hard problems engineers currently approximate — would have exact polynomial solutions. Most computer scientists bet against: Scott Aaronson's poll of the field puts >80% on P ≠ NP. But neither a proof nor a refutation exists. The class containment we do know is P ⊆ NP ⊆ PSPACE ⊆ EXP, with P ⊊ EXP proved by the time hierarchy theorem — so at least one of those containments is strict, but nobody knows which.

Step four · The $1 million prize

Clay Millennium Problem, 2000

The Clay Mathematics Institute named P vs NP one of the seven Millennium Prize Problems in May 2000, with a $1 000 000 award for a correct resolution either way. It is the only one of the seven that touches everyday technology directly. Dozens of false proofs are circulated every year — Vinay Deolalikar's 2010 announcement was the most prominent recent attempt and unravelled within weeks. The community-wide expectation is that the answer is P ≠ NP. The unsolved question is not what the answer is, but why — and which fragment of mathematics will turn out to contain the right lower-bound technique. Forty-plus years of barriers (relativisation, natural proofs, algebrisation) say it will not come from any method we currently know.

Diagram · the complexity zoo, restricted view

P sits inside NP sits inside EXP. NP-complete is the hardest rim of NP.

P sits as a small disc inside NP. NP-complete problems are the hardest in NP — every other NP problem reduces to them. If a single NP-complete problem turned out to be in P, the rose disc would collapse into the cyan one and P would equal NP. The time hierarchy theorem already proves P ⊊ EXP, so at least one of the inclusions above is strict — we just don't know which.

Catalogue · canonical NP-complete problems

Solve any of these in polynomial time — solve them all.

SAT

Boolean satisfiability — the original Cook-Levin problem.

3-SAT

SAT with clauses of length 3. The canonical NP-complete.

Hamiltonian Path

Trace a path through the graph that lands on each vertex once and only once.

Subset Sum

Pick a sub-multiset summing to a target integer.

Graph Colouring

Colour vertices with k colours, no edge monochrome.

Clique

Find a complete subgraph of size k.

Travelling Salesman (decision)

Tour all cities within budget B.

Tetris / Solitaire

Optimal play — Demaine, Hohenberger, Liben-Nowell 2003.

Sudoku N×N

Generalised to n² × n² boards. Yato & Seta 2003.

Minesweeper consistency

Kaye 2000 — given a board, is it consistent?

All inter-reducible in polynomial time. 3-SAT is the canonical instance — the Explorer is a working DPLL solver on it.

Where you meet it

How and where this technique lives in the world today.

Cryptography

If P = NP, RSA, AES, all blockchain and TLS-protected traffic would be broken overnight — every modern digital secret depends on P ≠ NP being effectively true.

Optimisation

Logistics (UPS routing), chip design (place-and-route), and machine learning hyperparameter search rely on NP-hard problems being attacked heuristically because exact solutions are intractable.

AI / SAT solvers

Modern SAT/SMT solvers (Z3, MiniSat) routinely solve million-variable NP-hard instances thanks to clever heuristics, even though worst-case complexity is exponential.

Bioinformatics

Protein folding, genome assembly and phylogenetic tree reconstruction are all NP-hard — driving the field to invent approximation algorithms and AI methods (AlphaFold).

Open prize

One of seven Clay Millennium problems with a $1,000,000 prize for proof or disproof.