Mathematicians

Stephen Cook

Modern

Citation Formats

General Reference

Mathematics Atlas. "Stephen Cook." Accessed August 30, 2026. https://mathematics.interactiveatlas.org/mathematicians/stephen-cook.

APA Style

Mathematics Atlas. (n.d.). Stephen Cook. Retrieved August 30, 2026, from https://mathematics.interactiveatlas.org/mathematicians/stephen-cook

BibTeX

@misc{mathematicsatlas-stephen-cook,
  author = {Mathematics Atlas},
  title = {Stephen Cook},
  year = {2026},
  url = {https://mathematics.interactiveatlas.org/mathematicians/stephen-cook},
  note = {Accessed August 30, 2026}
}

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

Birth Date

1939-12-14 1

Birth Year

1939 1

Birthplace

Buffalo, New York, United States 1

Nationality / Culture

American-Canadian 1

Defining Contribution

Formalized 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 Work

The Complexity of Theorem-Proving Procedures (1971); Logical Foundations of Proof Complexity (with Phuong Nguyen) 3

Award

ACM 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

Cross-Tradition Connections