Stephen Arthur Cook is a complexity theorist whose work helped found the modern study of computational hardness. His University of Toronto page, where he is listed as University Professor Emeritus in the Theory Group, describes his 1971 paper “The Complexity of Theorem Proving Procedures” as establishing NP-completeness, a cornerstone concept of computer science.
In that paper Cook introduced the notion of polynomial-time reducibility and proved that the satisfiability problem is NP-complete, meaning every problem in NP can be reduced to it. This single result reframed a sprawling collection of hard combinatorial problems as instances of one underlying question and set the agenda for complexity theory for the decades that followed.
Cook also articulated the P vs NP problem and remained closely tied to it. His Toronto page records that he wrote a manuscript titled “The P versus NP Problem” in 2000, prepared as the official problem description for the Clay Mathematics Institute’s Millennium Prize Problems.
For this body of work Cook received the ACM A.M. Turing Award in 1982, cited for advancing our understanding of the complexity of computation in a significant and profound way. His later research, including the book “Logical Foundations of Proof Complexity” co-authored with Phuong Nguyen, extended into proof complexity and the formal theories underlying efficient computation.