World Library  
Flag as Inappropriate
Email this Article

Stephen Cook

Article Id: WHEBN0000039432
Reproduction Date:

Title: Stephen Cook  
Author: World Heritage Encyclopedia
Language: English
Subject: Gordon Cook, P versus NP problem, Random-access stored-program machine, SC (complexity), Karp's 21 NP-complete problems
Collection: 1939 Births, American Computer Scientists, American Emigrants to Canada, Fellows of the Association for Computing MacHinery, Fellows of the Royal Society, Fellows of the Royal Society of Canada, Harvard University Alumni, Living People, Members of the Order of Ontario, Members of the United States National Academy of Sciences, Officers of the Order of Canada, Turing Award Laureates, University of California, Berkeley Faculty, University of Michigan Alumni, University of Toronto Faculty
Publisher: World Heritage Encyclopedia

Stephen Cook

Stephen Arthur Cook
Born (1939-12-14) December 14, 1939
Buffalo, New York
Fields Computer Science
Institutions University of California, Berkeley
University of Toronto
Alma mater Harvard University
University of Michigan
Doctoral advisor Hao Wang
Doctoral students Paul Beame
Mark Braverman
Valentine Kabanets
Toniann Pitassi
Robert A. Reckhow
Walter Savitch
Known for NP-completeness
Propositional proof complexity
Cook-Levin theorem
Notable awards Turing Award (1982)
CRM-Fields-PIMS prize (1999)
John L. Synge Award (2006)
Bernard Bolzano Medal
Gerhard Herzberg Canada Gold Medal for Science and Engineering (2012)

Stephen Arthur Cook, OOnt (born December 14, 1939) is a renowned American-Canadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity including co-discovering the theory of NP-completeness with Leonid Levin. He is currently a University Professor at the University of Toronto, Department of Computer Science and Department of Mathematics.


  • Biography 1
  • Research 2
    • Some Other Contributions 2.1
  • Awards and honors 3
  • Personal life 4
  • References 5
  • External links 6


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 until 1970 when he was denied reappointment. 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.


Stephen Cook is considered one of the forefathers of computational complexity theory.

During his PhD, Cook worked on complexity of functions, mainly on multiplication. In his seminal 1971 paper "The Complexity of Theorem Proving Procedures",[2][3] Cook formalized the notions of polynomial-time reduction (a.k.a. Cook reduction) and NP-completeness, and proved the existence of an NP-complete problem by showing that the Boolean satisfiability problem (usually known as SAT) is NP-complete. This theorem was proven independently by Leonid Levin in the Soviet Union, and has thus been given the name 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.

In his "Feasibly Constructive Proofs and the Propositional Calculus"[6] paper published in 1975, he introduced the equational theory PV (standing for Polynomial-time Verifiable) to formalize the notion of proofs using only polynomial-time concepts. 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",[7] in which they formalized the notions of p-simulation and efficient propositional 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".[8]

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.

Some Other Contributions

He named the complexity class NC after Nick Pippenger. The complexity class SC is named after him.[9] The definition of the complexity class AC0 and its hierarchy AC are also introduced by him.[10]

According to Don Knuth the KMP algorithm was inspired by Cook's automata for recognizing concatenated palindromes in linear time.[11]

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.

Cook won the ACM Turing Award in 1982. Association for Computing Machinery honored him as a Fellow of ACM in 2008 for his fundamental contributions to the theory of computational complexity.[12]

Government of Ontario appointed him to the Order of Ontario in 2013, the highest honor in Ontario.[13] He has won the 2012 Gerhard Herzberg Canada Gold Medal for Science and Engineering, the highest honor for scientist and engineers in Canada.[14] The Herzberg Medal is awarded by NSERC for ``for both the sustained excellence and overall influence of research work conducted in Canada in the natural sciences or engineering.[15]

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

Personal life

Cook currently lives with his wife in Toronto. They have two children named Gordon and James.[16] He plays the violin and enjoys sailing. He is often called Steve, or Stephen Cook.


  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. ^ "Feasibly Constructive Proofs and the Propositional Calculus" on ACM
  7. ^ "The Relative Efficiency of Propositional Proof Systems" on JStore
  8. ^ "Logical Foundations of Proof Complexity"'s official page
  9. ^ Steve's class": origin of SC""". Theoretical Computer Science - Stack Exchange. 
  10. ^ "Who introduced the complexity class AC?". Theoretical Computer Science - Stack Exchange. 
  11. ^ "Twenty Questions for Donald Knuth". 
  12. ^ Stephen Cook on ACM Fellows
  13. ^ "25 Appointees Named to Ontario's Highest Honour". Ministry of Citizenship and Immigration. 
  14. ^ Emily, Chung (February 27, 2013). "Computer scientist wins Canada's top science prize". Retrieved February 27, 2013. 
  15. ^ "Current Winner - 2012 - Stephen Cook". 
  16. ^ "Stephen A. Cook - Home Page". 

External links

  • Home page of Stephen A. Cook
  • ‘P versus NP’ and the Limits of Computation - Public lecture given by Stephen Cook at the University of Toronto
  • Oral history interview with Stephen Cook at Charles Babbage Institute, University of Minnesota. Cook discussed his education at the University of Michigan and Harvard University and early work at the University of California, Berkeley, and his growing interest in problems of computational complexity. Cook recounted his move to the University of Toronto in 1970 and the reception of his work on NP-completeness, leading up to his A.M. Turing Award.
  • Stephen Cook at the Mathematics Genealogy Project
  • Stephen Cook at DBLP
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.