The Full Wiki

Stephen Cook: Wikis


Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.


From Wikipedia, the free encyclopedia

Stephen Arthur Cook

Born December 14, 1939 (1939-12-14) (age 70)
Buffalo, New York
Fields Computer Science
Institutions University of California, Berkeley
University of Toronto
Alma mater Harvard University
Doctoral advisor Hao Wang
Doctoral students Paul Beame
Mark Braverman
Patrick Dymond
Leslie M. Goldschlager
Arvind Gupta
Valentine Kabanets
Bruce Kapron
Antonina Kolokolova
Anna Lubiw
Pierre McKenzie
Tsuyoshi Morioka
Phuong The Nguyen
Toniann Pitassi
Francois Pitt
Robert A. Reckhow
Walter Savitch
Alan Skelley
Michael Soltys
Known for NP-completeness
Propositional proof complexity
Notable awards Turing Award
CRM-Fields-PIMS prize
John L. Synge Award
Bernard Bolzano Medal

Stephen Arthur Cook (December 14, 1939, Buffalo, New York) is a renowned American-Canadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity. He is currently a University Professor at the University of Toronto, Department of Computer Science and Department of Mathematics.



Cook received his Bachelor's degree in 1961 from the University of Michigan, and his Master's degree and Ph.D. from Harvard University, respectively in 1962 and 1966. He joined the University of California, Berkeley, mathematics department in 1966 as an Assistant Professor, and stayed there till 1970 when he was infamously denied tenure. In a speech celebrating the 30th anniversary of the Berkeley EECS department, fellow Turing Award winner and Berkeley professor Richard Karp said that, "It is to our everlasting shame that we were unable to persuade the math department to give him tenure." [1] Cook joined the faculty of University of Toronto, Computer Science and Mathematics Departments in 1970 as an Associate Professor, where he was promoted to Professor in 1975 and University Professor in 1985.


Cook formalized the notion of NP-completeness in his seminal 1971 paper "The Complexity of Theorem Proving Procedures"[2][3], where he proved the existence of an NP-complete problem by showing that the Boolean satisfiability problem (usually known as SAT) is NP-complete. This theorem is known as Cook's theorem. (The NP-completeness of SAT was proven independently by Leonid Levin in the Soviet Union, and is therefore often called the Cook-Levin theorem.) The paper also formulated the most famous problem in computer science, the P vs. NP problem. Informally, the "P vs. NP" question asks whether every optimization problem whose answers can be efficiently verified for correctness/optimality can be solved optimally with an efficient algorithm. Given the abundance of such optimization problems in everyday life, a positive answer to the "P vs. NP" question would likely have profound practical and philosophical consequences.

Cook conjectures that there are optimization problems (with easily checkable solutions) which cannot be solved by efficient algorithms, i.e., P is not equal to NP. This conjecture has generated a great deal of research in computational complexity theory, which has considerably improved our understanding of the inherent difficulty of computational problems and what can be computed efficiently. Yet, the conjecture remains open and is among the seven famous Millennium Prize Problems [4][5].

In 1982, Cook received the prestigious Turing award for his contributions to complexity theory. His citation reads:

For his advancement of our understanding of the complexity of computation in a significant and profound way. His seminal paper, The Complexity of Theorem Proving Procedures, presented at the 1971 ACM SIGACT Symposium on the Theory of Computing, laid the foundations for the theory of NP-Completeness. The ensuing exploration of the boundaries and nature of NP-complete class of problems has been one of the most active and important research activities in computer science for the last decade.

He made another major contribution to the field in his 1979 paper, joint with his student Robert A. Reckhow, "The Relative Efficiency of Propositional Proof Systems" [6], in which they formalized the notion of efficient proof system, which started an area now called propositional proof complexity. They proved that the existence of a proof system in which every true formula has a short proof is equivalent to NP = coNP. Cook co-authored a book with his student Phuong The Nguyen in this area titled "Logical Foundations of Proof Complexity". [7]

His main research areas are complexity theory and proof complexity, with excursions into programming language semantics, parallel computation, and artificial intelligence. Other areas which he has contributed to include bounded arithmetic, bounded reverse mathematics, complexity of higher type functions, complexity of analysis, and lower bounds in propositional proof systems.

Awards and Honors

Cook was awarded a Steacie Fellowship in 1977, a Killam Research Fellowship in 1982, and received the CRM-Fields-PIMS prize in 1999. He has won John L. Synge Award and Bernard Bolzano Medal, and is a fellow of the Royal Society of London and Royal Society of Canada. Cook was elected to membership in the National Academy of Sciences (United States) and the American Academy of Arts and Sciences. Association for Computing Machinery honored him as a Fellow of ACM in 2008 for his fundamental contributions to the theory of computational complexity [8].

Cook has supervised numerous MSc students, and 28 PhD students have completed their degrees under his supervision.


Cook plays violin and enjoys sailing.


  1. ^ A Personal View of Computer Science at Berkeley - Richard Karp
  2. ^ "The Complexity of Theorem Proving Procedures", PDF file of a scanned version
  3. ^ "The Complexity of Theorem Proving Procedures", PDF file of a retyped version
  4. ^ P vs. NP problem on Millennium Prize Problems page - Clay Mathematics Institute
  5. ^ P vs. NP problem's official description by Stephen Cook on Millennium Prize Problems
  6. ^ "The Relative Efficiency of Propositional Proof Systems" on JStore
  7. ^ "Logical Foundations of Proof Complexity"'s official page
  8. ^ Stephen Cook on ACM Fellows

External links




Got something to say? Make a comment.
Your name
Your email address