1982 · Theory & algorithms
NP-completeness connected apparently different difficult problems.
Visual guide
Supply a candidate solution.
Verify it efficiently.
Translate another problem into SAT.
Reductions reveal a shared structure behind many search problems and help explain why finding exact solutions can be difficult.
NP-completeness does not prove that every instance is difficult or settle whether P equals NP.
01 · The idea
Stephen Cook established a foundation of NP-completeness by showing the special role of Boolean satisfiability. A proposed solution to an NP problem can be checked efficiently. Cook’s result showed how every problem in that class can be translated into satisfiability with only polynomial overhead.
Reductions reveal a shared structure behind many search problems and help explain why finding exact solutions can be difficult.
02 · The people
Stephen Cook gave computer science a precise way to compare the difficulty of computational problems. He showed that Boolean satisfiability is NP-complete, meaning that every problem in NP can be transformed into it efficiently. At the University of Toronto, his research helped establish complexity theory as a foundation for understanding feasible computation. The result does not settle whether P equals NP, which remains a separate question.
Read the biography ↗03 · Read further
Original explanations based on the official award record. The subject label is an editorial navigation aid.
Complexity theory connected random choices with some of computation’s deepest limits.
The story
Numerical libraries connect mathematical algorithms with changing hardware.
The story