P vs NP

1Fast and slow, measured properly

"Fast" depends on the computer, so theorists measure something steadier: how the number of steps grows as the input gets bigger. Call the input size $n$. For Subset Sum, $n$ is how many numbers are in the list.

An algorithm runs in polynomial time if its steps grow like $n^2$, $n^3$ or $n$ to some other fixed power. Checking a Subset Sum answer takes about $n$ additions, which is polynomial. Trying every group of numbers takes $2^n$ checks, because each number is either in or out. That is exponential time: add one number and the work doubles.

The difference is enormous. At $n = 10$, $n^2$ is 100 and $2^n$ is 1,024: close. At $n = 60$, $n^2$ is 3,600 while $2^n$ is about $1.15 \times 10^{18}$. A billion steps a second clears the first in a few millionths of a second and the second in more than 36 years.

In the 1960s, Alan Cobham and Jack Edmonds proposed polynomial time as the working meaning of "efficient". Edmonds called such algorithms "good algorithms". The idea stuck because it does not depend on which computer you use.

2Machines, inputs and the worst case

To prove anything about every possible program, you need a precise model of a program. The standard one is the Turing machine, introduced by Alan Turing in 1936: a simple device that reads and writes symbols on a tape, one step at a time. Anything a laptop can compute, a Turing machine can compute too.

An input is a string of symbols from a finite alphabet $\Sigma$, such as $\{0,1\}$. The running time of a machine $M$ is judged by its worst case: the most steps it ever takes on any input of length $n$. That worst case is written $T_M(n)$.

This matters. A method that is quick on most inputs but painfully slow on a few does not count as polynomial. P is about guarantees for every input, however nasty.

3Two classes: P and NP

P is the set of yes/no problems that some Turing machine solves within $n^k + k$ steps, for some fixed $k$. Sorting a list, finding the shortest route on a map and testing whether a number is prime are all in P. The last one was only proved in 2002, by Manindra Agrawal, Neeraj Kayal and Nitin Saxena.

NP is the set of yes/no problems where every yes answer has a short certificate that can be checked in polynomial time. Subset Sum is in NP: the certificate is the group of numbers. Sudoku is in NP: the certificate is the filled grid.

Anything you can solve fast, you can also check fast: just solve it again and compare. So P sits inside NP. The question is whether NP contains anything that P does not.

4The hardest problems in NP

In 1971 Stephen Cook showed that one problem, SAT, is as hard as anything in NP. SAT asks whether a logic formula built from AND, OR and NOT can be made true by some choice of true/false values. Cook proved that every NP problem can be translated quickly into SAT. Leonid Levin found the same idea independently in the Soviet Union and published it in 1973.

Problems with this property are called NP-complete. In 1972 Richard Karp showed that 21 natural problems are NP-complete, and he introduced the names P and NP. By 1979 Michael Garey and David Johnson's book listed about 300. Today there are thousands, including Subset Sum, colouring a map with three colours and finding a route that visits every city exactly once.

They all stand or fall together. A fast algorithm for any single NP-complete problem would give a fast algorithm for every problem in NP. Decades of effort by mathematicians, programmers and industry have found no such algorithm for any of them.

5Smarter than brute force, but still not fast

Brute force is not the only way to attack Subset Sum. A trick called meet in the middle splits the list in half, lists every sum of each half and matches them up. That needs about $2^{n/2}$ steps: a huge improvement, but still exponential.

Another method, dynamic programming, is fast when the numbers themselves are small, because it tracks which totals are reachable. When the numbers are hundreds of digits long, it slows down badly. No known method stays polynomial on every input.

The same story repeats for SAT. Cook's official problem description cites the best known algorithms for 3-SAT (SAT with three values per clause) at roughly $1.5^n$ steps. Later improvements are small. Clever ideas shave the exponent, but none has removed it.

That is the heart of the problem. Showing that brute force is slow is easy. Showing that every possible algorithm, including ones nobody has invented, must be slow is what nobody can do.

6What lies between

If P and NP are different, is every NP problem either easy (in P) or hardest (NP-complete)? No. In 1975 Richard Ladner proved that if P ≠ NP, there must be NP problems in between: harder than P, but not NP-complete.

Two natural suspects are factoring (splitting a large number into primes) and graph isomorphism (telling whether two networks are the same network with the dots rearranged). In 2015 László Babai announced a quasi-polynomial algorithm for graph isomorphism, much faster than before. Harald Helfgott found an error; Babai withdrew the claim on 4 January 2017 and announced a fix five days later.

Factoring has no known fast algorithm on ordinary computers, and much of internet security depends on that. But factoring is not believed to be NP-complete, so even a fast factoring method would not settle P vs NP.

7What most experts believe

In 2019 Bill Gasarch ran his third poll of researchers on P vs NP and received 124 responses. About 80% believed P ≠ NP. Among those who had thought hardest about the problem, about 99% did.

The reasons are practical as much as mathematical. Thousands of NP-complete problems, attacked for fifty years by some of the best minds and by industries with billions at stake, have never yielded a fast method. If P = NP, it would be strange that nobody has stumbled on a single example.

But belief is not proof. Primality testing looked hard for centuries and turned out to be in P. The million dollars is for a proof, and the proof is exactly what is missing.