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
Source Time hierarchy theorem (Wikipedia)
In the Other Atlases
Same As
Also in Computing Atlas: the same subject.
Nationality
Also in Geography Atlas: the nationality of this subject.
Source Stephen Cook (Wikipedia)tier 2
Also in Geography Atlas: the nationality of this subject.
Source Stephen Cook (Wikipedia)tier 2
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
Time hierarchy theorem (Wikipedia)
Proofs Credited: Time Hierarchy Theorem, LeadQuote, Proofs Credited: Time Hierarchy Theorem, Lead
The time hierarchy theorem for nondeterministic Turing machines was originally proven by Stephen Cook in 1972.
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.