On this page
In May 1971, Stephen Cook presented a short paper, The complexity of theorem-proving procedures, at the third ACM Symposium on Theory of Computing in Shaker Heights, Ohio. It showed that one puzzle about true-and-false statements carries the difficulty of a whole family of problems. Fifty-five years on, nobody knows whether that family can be solved quickly.
What did Stephen Cook prove in 1971?
Cook's own account is in The P versus NP problem, the official problem description he wrote for the Clay Mathematics Institute. He writes that the main results of the 1971 paper were that several natural problems, "including Satisfiability and 3-SAT", are NP-complete.
Satisfiability, or SAT, asks one question: given a logical formula built from variables joined by AND, OR and NOT, is there a way of setting each variable to true or false that makes the whole formula true?
Cook's method was a translation. For any problem whose answers a program can check quickly, he showed how to turn each instance, in polynomial time, into a formula that is satisfiable exactly when the answer is yes. So a fast method for SAT would give a fast method for all of them. That is what NP-complete means: in NP, and at least as hard as everything else in NP.
What is the difference between P and NP?
The Clay Mathematics Institute puts it plainly: P means "easy to find" and NP means "easy to check", and Cook and Leonid Levin formulated the question independently in 1971.
Cook's essay gives clean examples. Deciding whether a number is a perfect square is in P, because Newton's method finds square roots fast. Deciding whether a number is composite is in NP, because if someone hands you a divisor, one division checks it.
Every problem in P is also in NP: if you can find an answer fast, you can check one fast. The open question is the reverse. Does P equal NP?
Why does one problem stand for so many?
A year after Cook, Richard Karp's Reducibility among combinatorial problems (1972) used Cook's results to show, in Cook's words in the Clay essay, that "20 other natural problems are NP-complete". Levin independently defined a similar notion, the universal search problem.
The list kept growing. Cook notes that many hundreds of NP-complete problems are known, and that the standard reference book lists 300 in its appendix. They include colouring the points of a network with 3 colours so that linked points differ, finding a route that visits every city once and returns home (a Hamiltonian cycle), and picking numbers from a set that add up to a target.
If graphs are new to you, start with how Euler's Königsberg bridges began graph theory.
Try it: Cook's own satisfiability example
Here is the 3-SAT formula Cook uses in his essay, with four variables P, Q, R and S. All four clauses must be true at once.
(P or Q or R)
and (not P or Q or not R)
and (P or not Q or S)
and (not P or not R or not S)
Step 1, checking. Cook gives an answer: P and Q true, R and S false. Clause 1 holds because P is true. Clause 2 holds because Q is true. Clause 3 holds because P is true. Clause 4 holds because R is false, so "not R" is true. That is NP: a proposed answer is easy to verify.
Step 2, finding. Now start from nothing. Four variables give 2 × 2 × 2 × 2 = 16 possible settings, so trying them all is fine. But each extra variable doubles the count: 50 variables give 2 to the power 50, more than a million billion settings. Nobody has found a method proven to be fast on every formula.
Step 3, explaining it back. Tell a friend or parent, in two sentences, why checking is easy and finding seems hard. That is the heart of P versus NP.
If the AND and OR rules feel shaky, revise them with logic gate combination circuits, or look up Boolean logic in the Fermi Concept Library, which covers concepts in physics, chemistry, biology, mathematics and computing.
What would happen if someone proved P = NP?
The Clay Mathematics Institute announced its Millennium Prize Problems on 24 May 2000, with $1 million for the solution of each; P versus NP is one of them.
Cook's essay spells out the stakes. Internet security, including most financial transactions, rests on assumptions such as the difficulty of factoring large numbers; if P = NP, he writes, "these assumptions are all false". A practical method could also let a computer find a formal proof of any theorem that has a reasonably short proof.
A habit worth stealing from all this: when a long problem feels impossible, ask separately how you would check an answer and how you would find one. The Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer, so you can check each step of your own method.
