01 · A life in computing
The person behind the work
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.
The contribution, explained
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.
Why it matters
Reductions reveal a shared structure behind many search problems and help explain why finding exact solutions can be difficult.