P vs NP

P vs NP asks whether every problem whose answer can be checked quickly can also be solved quickly. Verifying a completed sudoku takes a minute; producing that solution can take hours. If those two tasks are secretly equal in difficulty, most of modern cryptography collapses. The Clay Mathematics Institute will pay $1,000,000 to whoever settles the question, in either direction.

Checking is not the same as finding

Everyday life keeps the two tasks apart without anyone noticing. A finished jigsaw can be confirmed correct at a glance, while assembling its thousand pieces eats a weekend. A teacher marks an exam script in minutes that took the student two hours to write. A maths undergraduate can check a proof in an afternoon that took its discoverer years to find.

The demo above turns this gap into something you can measure. Pick chips that add up to the target and the page verifies your answer with a single addition, in about a microsecond. Ask the computer to find that answer from scratch and it has to grind through subsets, up to 1,048,576 of them for a hand of 20 chips. Checking stayed trivial. Finding blew up. P vs NP asks whether that blow-up is a law of nature or just a failure of imagination.

What P and NP mean

Both are classes of yes-or-no problems, defined on the model of computation Alan Turing set out in 1936, the same machine at the heart of the foundations of computer science.

P contains the problems a computer can solve in polynomial time: the number of steps grows like n squared or n cubed as the input grows. Sorting a list, finding the shortest route between two towns and testing whether a number is prime all live here. Polynomial growth is manageable. An n squared algorithm on 100 items needs about 10,000 steps, which a modern processor clears in about ten microseconds.

NP contains the problems whose answers can be verified in polynomial time when someone hands you a candidate solution. The name is short for nondeterministic polynomial, and despite appearances it does not mean “not polynomial”. Every problem in P is also in NP, because one way to check an answer is to solve the problem yourself and compare.

The trouble starts with problems where the only known way to find an answer is trying possibilities. With n items there can be 2 to the power n subsets to try. For n = 100 that is about 1.27 x 10^30. A machine testing a billion subsets per second would need roughly 40 trillion years, nearly 3,000 times the age of the universe. So the question is whether every problem in NP has a polynomial-time algorithm that nobody has found yet. Almost everyone bets no. Nobody can prove it.

Where the question came from

The earliest known statement is in a 1956 letter from Kurt Gödel to John von Neumann, who was then dying of cancer. Gödel asked whether proofs of theorems could be found in time proportional to n or n squared, and observed that if so, mathematicians could hand discovery over to machines. Von Neumann never replied as far as anyone knows, and the letter only surfaced decades later.

The formal problem arrived in 1971, when Stephen Cook’s paper The Complexity of Theorem-Proving Procedures proved that Boolean satisfiability, SAT, occupies a special position: every problem in NP can be translated into it in polynomial time. Leonid Levin reached the same result independently in the Soviet Union, publishing in 1973. A year after Cook, Richard Karp showed the idea had teeth. His 1972 paper Reducibility Among Combinatorial Problems listed 21 well-known problems, drawn from graph theory, scheduling and logic, that all share SAT’s special status.

NP-complete problems

Karp’s 21 problems are NP-complete, and the term repays a careful definition since it gets misused. A problem is NP-complete if it belongs to NP and every other problem in NP reduces to it in polynomial time. NP-complete problems are, in a precise sense, the hardest problems in NP.

That definition has a startling consequence. Find a polynomial-time algorithm for any single NP-complete problem and you get one for every problem in NP, because everything reduces to the problem you just cracked. One domino knocks down the whole line, and P equals NP. Equally, prove that any one NP-complete problem has no fast algorithm and you have proved P is not equal to NP.

Thousands of problems have joined the list since 1972. SAT was first. The travelling salesman problem is the most famous. Subset sum, the game in the demo above, appears on Karp’s original list under the name knapsack. Timetabling, protein design, sudoku generalised to n by n grids, even some questions about winning positions in games: reductions connect them all. A fast algorithm for the chips-and-target puzzle on this page would, quite literally, be worth the million dollars.

What would change if P equals NP

Suppose someone found a genuinely practical polynomial-time algorithm for an NP-complete problem. Public-key cryptography would fail, because deriving a private key from a public one is a checking problem of exactly this kind; the consequences for digital money are laid out in Breaking Bitcoin. Airlines, chip designers and delivery firms currently pay for approximate answers to optimisation problems that would suddenly have cheap exact ones. Predicting how proteins fold, a bottleneck in drug discovery, involves search problems of the same shape.

Mathematics itself might change most. Gödel’s 1956 letter already saw this: a short proof of a theorem is quick to verify, so finding short proofs is an NP problem. P equals NP would mean a computer could find any proof a human could check in reasonable time. The caveat matters, though. A proof that P equals NP could be non-constructive, or could yield an algorithm with running time n to the power 1,000, which counts as polynomial on paper and is useless in practice.

Why it is so hard to prove

Turing showed in 1936 that the halting problem cannot be solved at all, and his proof works by reasoning about one cleverly constructed program. P vs NP is harder to attack because a proof must say something about every possible efficient algorithm, including techniques nobody has invented. Complexity theorists have even proved that whole categories of argument cannot work. In 1975 Baker, Gill and Solovay showed that proofs which relativise, meaning they stay valid when every machine gets the same magic oracle, can never settle the question, which rules out the diagonalisation tricks that killed the halting problem. In the 1990s Razborov and Rudich showed that “natural proofs”, the family covering most known circuit lower bounds, would break cryptographic generators that are widely believed secure. Any successful proof has to slip past both barriers. None has.

The million dollars and the graveyard

In 2000 the Clay Mathematics Institute named P vs NP one of its seven Millennium Prize Problems, each carrying a $1,000,000 award. A winning solution must appear in a qualifying refereed publication and survive two years of scrutiny from the mathematical community first.

The prize has drawn a crowd. Gerhard Woeginger, a complexity theorist at Eindhoven and later Aachen, kept a public list of claimed solutions from 1986 until 2016. It recorded 116 attempts: 61 claiming P equals NP, 49 claiming the opposite, and 6 arguing for something else entirely, such as the question being unprovable. Not one has held up. Meanwhile the field’s collective judgement is lopsided; in William Gasarch’s 2019 poll of complexity researchers, 88 per cent expected P is not equal to NP. Lance Fortnow, asked to summarise the problem’s status for the Communications of the ACM, noted the honest report was two words long: still open.

Half a century after Cook’s paper, the gap you can feel in the demo above, one addition to check against a million subsets to search, is still only a feeling. Nobody has proved the wall is real, and nobody has found a way through it.