The 1971 paper titled The Complexity of Theorem Proving Procedures established the formal foundations for the P versus NP problem, a central question in computer science that remains unsolved today. Authored by Stephen Cook, this work introduced the concept of NP-completeness, changing how mathematicians and computer scientists categorize the inherent difficulty of computational tasks.
Academic Foundation
Born in Buffalo in 1939, Cook pursued his higher education in the United States. He earned a bachelor's degree from the University of Michigan in 1961, followed by a master's degree and a Doctor of Sciences from Harvard University in 1962 and 1966, respectively. He began his teaching career as an assistant professor at the University of California, Berkeley, in 1966. Following his departure in 1970, he joined the University of Toronto, where he served in the departments of computer science and mathematics, eventually becoming a Distinguished Professor.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →Computational Complexity
Cook’s research focuses primarily on complexity theory and proof complexity. His seminal work on the Boolean satisfiability problem, or SAT, demonstrated that this problem is NP-complete, a discovery mirrored independently by Leonid Levin and now recognized as the Cook–Levin theorem. His contributions also include defining the complexity classes NC, SC, and AC0. Beyond complexity, he has investigated parallel computation, programming language semantics, and bounded arithmetic.
Professional Recognition
His work has earned significant international accolades, including the 1982 ACM Turing Award for advancing the understanding of computational complexity. He is a fellow of the Association for Computing Machinery and a member of prestigious bodies including the Royal Society, the National Academy of Sciences, and the American Academy of Arts and Sciences. In Canada, he received the Gerhard Herzberg Canada Gold Medal for Science and Engineering in 2012 and was appointed an Officer of the Order of Canada in 2015.
Fast facts
- Born: 1939, Buffalo
- Citizenship: Canada and United States
- Turing Award: 1982
- Degree: Doctor of Sciences
- Academic Home: University of Toronto
- Notable Recognition: Officer of the Order of Canada
- Research Field: Computational complexity
Questions readers ask
What is the P vs. NP problem?
It is a question asking if every decision problem with efficiently verifiable answers can also be solved by an efficient algorithm.
What is the Cook-Levin theorem?
It is the formal proof that the Boolean satisfiability problem is NP-complete, established independently by Stephen Cook and Leonid Levin.
Achievements
- Turing Award — 1982
- Affiliated with University of Toronto and University of California, Berkeley
- Educated at Harvard University and University of Michigan
- Worked as computer scientist, university teacher and mathematician
