University Professor Emeritus in the Department of Computer Science at the University of Toronto, where he has taught computational complexity and computability for decades. His 1971 paper, The Complexity of Theorem-Proving Procedures, presented at the Third ACM Symposium on Theory of Computing, formalized the notion of NP-completeness for the first time and proved that Boolean satisfiability (SAT) is NP-complete, the founding result of the theory of computational complexity. He is a recipient of the 2008 CRM-Fields-PIMS Prize.
Facts
BirthplaceBuffalo, New York, United States 1 Nationality / Culture Defining ContributionFormalized NP-completeness in 1971, independently of and roughly contemporaneously with Leonid Levin's 1973 work in the Soviet Union; the result that Boolean satisfiability is NP-complete is now known as the Cook-Levin theorem, the founding theorem of computational complexity theory and the basis for the P versus NP question. 2 Notable WorkThe Complexity of Theorem-Proving Procedures (1971); Logical Foundations of Proof Complexity (with Phuong Nguyen) 3 AwardACM A.M. Turing Award (1982); Gerhard Herzberg Canada Gold Medal (2012); Officer of the Order of Canada (2015); Fellow, Royal Society of London and Royal Society of Canada. 1 Connections
Conjectures Posed
Formalized 1971; Leonid Levin independently formalized the same question in the Soviet Union, published 1973.
Source Clay Mathematics Institute
In Branch
Source Stephen Cook, Faculty Homepage, University of Toronto
Source Stephen Cook, Faculty Homepage, University of Toronto
Proofs Credited
In the Other Atlases
- Also in Computing Atlas: Stephen Cook, the same subject.
- Also in Geography Atlas: Canada, nationality there.
- Also in Geography Atlas: United States, nationality there.
Sources
1. Stephen Cook (Wikipedia)
Wikimedia Foundationopening paragraph
Stephen Arthur Cook (born December 14, 1939) is an American-Canadian computer scientist and mathematician.
Awards section
In 1982, Cook received the Turing Award for his contributions to complexity theory.
Lead section, gender reference
He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.
View the Source 2. Clay Mathematics Institute
Clay Mathematics Institute
3. Stephen Cook, Faculty Homepage, University of Toronto
University of Toronto, Department of Computer Science
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.