Checking an answer is easy; finding one seems hard. Polynomial against exponential growth, and the map of complexity classes
P is the class of problems a computer can solve in polynomial time. NP is the class whose yes-answers can be checked in polynomial time, given the right certificate. Is every problem whose answers are quick to check also quick to solve? Nobody knows — it is one of the seven Millennium Prize problems, with a million dollars waiting for the answer.
Tap tiles to make a subset that hits the target — checking is instant. Then press Search and watch brute force grind through 2ⁿ subsets, and compare meet in the middle.
Values are random up to about 2ⁿ, and a hidden subset fixes the target (orange line), so a solution always exists and usually only a few do. Pink tiles are yours, white tiles are the search’s current guess, green means the sum hits the target. Brute force walks the 2ⁿ subsets in Gray-code order, one addition or subtraction per step; up to n = 26 it really runs to the end, above that it samples and extrapolates. The cost bars share one log scale.
A problem is in NP if every yes-instance has a certificate (or witness) — a short piece of evidence that a polynomial-time verifier accepts — while no-instances have none. For Subset Sum the certificate is the subset itself, and the verifier adds it up: at most n additions. The name NP stands for nondeterministic polynomial time: a machine that could guess the certificate would solve the problem quickly. P ⊆ NP, since a problem you can solve quickly you can certainly check quickly.
Subset Sum is NP-complete — it is on Richard Karp’s 1972 list of 21 NP-complete problems, under the name knapsack — so a polynomial-time algorithm for it would give one for every problem in NP. Yet it can be solved in time proportional to n·T by dynamic programming, where T is the target: keep a table of which sums from 0 to T are reachable. That is pseudo-polynomial: polynomial in the magnitude of the numbers, but exponential in the number of digits needed to write them down. The hardness lives in numbers with many digits, which is why this demo draws values up to about 2ⁿ.
Meet in the middle (Ellis Horowitz and Sartaj Sahni, 1974) splits the numbers into two halves, lists the 2^(n/2) subset sums of each, sorts both lists and scans them with two pointers. That is roughly the square root of brute force, and decades later the worst-case running time for general Subset Sum has not been improved to 2^((1/2 − ε)n) for any ε > 0. It is still exponential: each extra number multiplies the work by about √2.
Slide the time budget from a millisecond to the age of the universe, then buy a faster machine. The polynomial bars leap ahead; the exponential ones barely move.
One step per unit of cost, 10⁹ steps a second before any speed-up. Blue bars are polynomial; amber (1.307ⁿ, about the best known worst-case bound for 3-SAT, from PPSZ), white (2ⁿ, brute force) and rose (n!) are exponential or worse. Dashed outlines show the ×1 machine. Drag the lower chart up or down to move the budget line; dots mark where each curve crosses it.
In 1965 Alan Cobham and Jack Edmonds independently proposed polynomial time as the mathematical meaning of “efficiently solvable” — now called the Cobham–Edmonds thesis. Its great virtue is robustness: the class P is the same whichever reasonable model of computation you use, and polynomials are closed under composition, so an efficient algorithm that calls an efficient subroutine is still efficient. Tables like the one above, contrasting n, n², 2ⁿ and their brethren, were made famous by Michael Garey and David Johnson’s 1979 book Computers and Intractability.
The thesis is a convention, not a theorem. An n¹⁰⁰ algorithm is polynomial and useless; a 1.0001ⁿ algorithm is exponential and fine for any input you will ever meet. In practice, though, natural problems that turn out to be in P usually end up with algorithms of small exponent after further work, while exponential algorithms meet a hard wall: a computer a thousand times faster adds only about ten to the input size a 2ⁿ algorithm can handle, but multiplies the n² reach by about 31.6.
Some separations are actually proved. The time hierarchy theorem of Juris Hartmanis and Richard Stearns (1965) shows that more time lets you solve strictly more problems; in particular P ≠ EXP, where EXP is the class of problems solvable in time 2 to a polynomial in n. So some problems provably need exponential time. What nobody can prove is that any NP problem does.
Tap problems to send them to the class where they live, and read why. Then imagine P = NP, or P ≠ NP, and watch the map rearrange.
Nested regions mean proved inclusions; the shaded rims hold the complete problems, the hardest in each class. Exactly where the boundaries lie is mostly unknown: the picture is drawn as most researchers believe it to be (P ≠ NP and NP ≠ coNP), and every one of these classes could in principle collapse into its neighbour except P and EXP. Tap the relations to light up the boundaries they are about.
What is proved: P ⊆ NP ⊆ PSPACE ⊆ EXP, and P ≠ EXP. So at least one of the three inclusions is strict, but nobody knows which. P versus NP, NP versus coNP and NP versus PSPACE are all open. The question was made one of the seven Millennium Prize problems by the Clay Mathematics Institute in 2000, with a prize of one million dollars.
Several of the natural ways to attack it are known to fail. Theodore Baker, John Gill and Robert Solovay (1975) showed that there are oracles relative to which P = NP and others relative to which P ≠ NP, so any proof technique that “relativises” — works unchanged when every machine is given the same oracle, as diagonalisation does — cannot settle the question. Alexander Razborov and Steven Rudich (1994) showed that “natural proofs”, the style behind the known circuit lower bounds, cannot prove strong enough lower bounds if secure pseudorandom functions exist. Scott Aaronson and Avi Wigderson (2008) identified a third barrier, algebrization, that also catches the algebraic techniques, such as arithmetisation, which get around relativisation.
Most researchers believe P ≠ NP. William Gasarch’s polls of theorists in 2002, 2012 and 2019 each found a majority expecting P ≠ NP. That is a belief, not evidence of proof: if it is right, Ladner’s theorem (1975) guarantees problems in NP that are neither in P nor NP-complete, but proving any particular problem — factoring, say, or graph isomorphism — to be one of them would itself prove P ≠ NP.
Spot a mistake or have an idea?