The story
In 1971 the computer scientist Stephen Cook, then at the University of Toronto, presented a paper called 'The Complexity of Theorem-Proving Procedures' at a conference in Shaker Heights, Ohio. It showed that a particular problem, deciding whether a logical formula can be made true by some assignment of true and false values (the satisfiability problem), is 'NP-complete.' Every problem in a huge class could be turned into this one. The Soviet mathematician Leonid Levin independently reached the same result, published in 1973.
Computer scientists sort problems by how fast the best method grows with size. Class P holds problems that a computer can solve in 'polynomial time,' meaning the running time grows manageably, like the square of the input size. Class NP holds problems where, if someone hands you a proposed answer, you can check it quickly, even if finding it may be hard. A Sudoku is a good example, because a filled grid is quick to verify, but solving a hard one from scratch can seem to take much more work. The foundations were Alan Turing's 1936 model of computation and 1960s work by Hartmanis, Stearns and Jack Edmonds, who argued that polynomial time marks a 'good' algorithm.
Cook's discovery meant that if anyone found a fast method for one NP-complete problem, every NP problem would become fast to solve. In 1972 Richard Karp showed that 21 well-known problems, including the traveling salesman problem and graph coloring, were NP-complete, and thousands more have been found since. Most experts believe P is not equal to NP, meaning some problems really are harder to solve than to check, but no one has proved it. A proof either way would reshape fields from logistics to cryptography. The Clay Mathematics Institute made P versus NP one of its seven Millennium Prize Problems in 2000, with a $1 million prize.
Why it mattered
- NP-completeness gave programmers a way to recognize problems with no known efficient solution, so they could stop searching for exact fast algorithms and use approximations.
- Computational complexity became a central branch of computer science, with its own theory of hard and easy problems.
- Public-key cryptography rests on the assumption that certain problems are hard, so the open question is tied to the security of online communication.
- Thousands of practical problems in scheduling, routing and circuit design were shown to be NP-complete, which shaped how engineers approach them.
- In 2000 the Clay Mathematics Institute listed P versus NP as a Millennium Prize Problem, which put it among the most famous unsolved questions in mathematics.
Sources
- The P versus NP Problem (Stephen Cook) Clay Mathematics Institute
- Stephen A. Cook, A.M. Turing Award Laureate ACM
Drafted by AI (Claude) from the sources above and checked against them by AI; no historian has reviewed this page. Spot a mistake? Suggest a correction. How pages are made
Community notes
Loading notes…