Stephen Cook
University Professor Emeritus, recipient of the A.M. Turing Award for formalizing NP-completeness.
Stephen Cook is a University Professor Emeritus at the University of Toronto, recognized for his foundational work in computational complexity theory. Born on December 14, 1939, this American-Canadian computer scientist and mathematician earned his bachelor’s degree from the University of Michigan in 1961, followed by a master’s degree and PhD from Harvard University’s mathematics department in 1962 and 1966, respectively. After a brief stint as an assistant professor at the University of California, Berkeley, where he was denied tenure, he joined the University of Toronto in 1970 as an associate professor, later becoming a full professor in 1975 and a distinguished professor in 1985. His seminal 1971 paper, “The Complexity of Theorem Proving Procedures,” formalized polynomial-time reduction and NP-completeness, proving that the Boolean satisfiability problem (SAT) is NP-complete—a result independently reached by Leonid Levin and now known as the Cook–Levin theorem. This paper also introduced the famous P versus NP problem, which asks whether every efficiently verifiable decision problem can also be efficiently solved. Cook conjectures that P does not equal NP, a question that remains open and is one of the seven Millennium Prize Problems. In 1975, he introduced the equational theory PV to formalize polynomial-time proofs, and in 1979, with student Robert Reckhow, he defined p-simulation and efficient propositional proof systems, founding the field of propositional proof complexity. They showed that a proof system with short proofs for all true formulas is equivalent to NP equaling coNP. Cook’s research spans complexity theory, proof complexity, bounded arithmetic, and parallel computation. He named the complexity class NC and has a class, SC, named after him. His honors include the 1982 ACM Turing Award, the 1999 Gödel Lecture, the 2012 Gerhard Herzberg Canada Gold Medal, and membership in the Royal Society of London and the U.S. National Academy of Sciences.
- known_for
- Formalizing NP-completeness, Cook–Levin theorem, P vs. NP problem
- awards
- ACM Turing Award (1982)
Verified Timeline
Quick Facts
- Honorific Suffix
- country=CAN · size=100% · sep= · OC · OOnt
- Birth Name
- Stephen Arthur Cook
- Birth Date
- 1939-12-14
- Birth Place
- Buffalo, New York
- Field
- Computer Science
- Workplaces
- University of Toronto / University of California, Berkeley
- Education
- University of Michigan (BA) / Harvard University (MA, PhD)
- Thesis Title
- On the Minimum Computation Time of Functions
- Thesis Url
- <!--(or
- Thesis1 Url
- and
- Thesis Year
- 1966
- Doctoral Advisor
- Hao Wang
Facts from the source article.
Lore & Background
Stephen Arthur Cook is an American-Canadian computer scientist and mathematician, born December 14, 1939, and a university professor emeritus at the University of Toronto, jointly appointed in the departments of Computer Science and Mathematics. He is regarded as a foundational figure in computational complexity theory. Cook earned his bachelor’s degree from the University of Michigan in 1961, followed by a master’s and PhD in mathematics from Harvard University in 1962 and 1966. After a period as an assistant professor at the University of California, Berkeley, from 1966 to 1970, he was denied reappointment—a decision later regretted by fellow Turing Award winner Richard Karp. He then joined the University of Toronto as an associate professor in 1970, becoming a full professor in 1975 and a Distinguished Professor in 1985. Cook’s defining contribution is his 1971 paper “The Complexity of Theorem Proving Procedures,” which formalized polynomial-time reduction and NP-completeness, proving that the Boolean satisfiability problem (SAT) is NP-complete—a result known as the Cook–Levin theorem. This work also introduced the P versus NP problem, a central open question in computer science and one of the seven Millennium Prize Problems. Cook conjectures that P does not equal NP. He later introduced the equational theory PV (Polynomial-time Verifiable) and, with student Robert Reckhow, formalized efficient propositional proof systems, founding the field of propositional proof complexity. He also named the complexity class NC and has the class SC named after him. Cook received the ACM Turing Award in 1982 for these foundational contributions.
Reader's Guide
Stephen Cook’s research has profoundly shaped computational complexity theory, particularly through his formalization of NP-completeness. In his landmark 1971 paper, he introduced polynomial-time reduction and proved that the Boolean satisfiability problem (SAT) is NP-complete, a result independently reached by Leonid Levin and now known as the Cook–Levin theorem. This work also formulated the P versus NP problem, which asks whether every decision problem with efficiently verifiable solutions can also be solved efficiently. Cook conjectures that P does not equal NP, a question that remains open and is one of the seven Millennium Prize Problems. His contributions extended to proof complexity: in 1975, he introduced the equational theory PV to formalize polynomial-time proofs, and in 1979, with Robert Reckhow, he defined p-simulation and efficient propositional proof systems, establishing that the existence of short proofs for all true formulas is equivalent to NP = coNP. Cook also named the complexity class NC and introduced the AC0 hierarchy; the class SC is named after him. His work on automata for recognizing concatenated palindromes inspired the KMP algorithm. A university professor emeritus at the University of Toronto, he received the 1982 ACM Turing Award for laying the foundations of NP-completeness, which became one of the most active research areas in computer science.
Did You Know?
- Stephen Cook introduced the unsolved problem of P versus NP in 1971.
- He received the A.M. Turing Award in 1982 for formalizing NP-completeness.
- Cook is a University Professor Emeritus at the University of Toronto.
- He is considered one of the forefathers of computational complexity theory.
Frequently Asked Questions
Who is Stephen Cook?
Stephen Arthur Cook (born December 14, 1939) is an American-Canadian computer scientist and mathematician who serves as professor emeritus at the University of Toronto. He is broadly regarded as a founding figure in computational complexity theory.
What is the Cook–Levin theorem?
The Cook–Levin theorem, published in 1971, rigorously demonstrated that Boolean satisfiability is NP-complete, making it the first problem formally shown to sit at the top of the NP class. This single result became the cornerstone on which the entire theory of NP-completeness was built.
How did Stephen Cook shape the P vs. NP problem?
By formalizing the notion of NP-completeness, Cook gave the field a precise framework for asking whether efficiently verifiable problems are also efficiently solvable. His 1971 work turned what had been a vague intuition into the central open question of theoretical computer science.
Why do fans call Stephen Cook a forefather of computational complexity theory?
Before his contributions, there was no rigorous taxonomy for ranking problems by how hard they are to compute. Cook's introduction of NP-completeness and the Cook–Levin theorem essentially created the language and structure that the discipline still uses today.
What major award did Stephen Cook receive?
In 1982, Cook was bestowed the ACM Turing Award, frequently compared to a Nobel Prize in computer science, specifically for his foundational work on computational complexity.
More in Mathematics And Cryptography 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record