The Info List - Stephen Cook

--- Advertisement ---

Stephen Arthur Cook, OC, OOnt (born December 14, 1939) is an 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
Computer Science
and Department of Mathematics.


1 Biography 2 Research

2.1 Some other contributions

3 Awards and honors 4 Personal life 5 See also 6 References 7 External links

Biography[edit] Cook received his Bachelor's degree
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, from the Mathematics
Department.[1] 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
Turing Award
winner and Berkeley professor Richard Karp
Richard Karp
said that, "It is to our everlasting shame that we were unable to persuade the math department to give him tenure."[2] 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 Distinguished Professor in 1985. Research[edit] Stephen Cook
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",[3][4] 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
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.[5][6] In 1982, Cook received the Turing award
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"[7] 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",[8] 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".[9] 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[edit] He named the complexity class NC after Nick Pippenger. The complexity class SC is named after him.[10] The definition of the complexity class AC0
and its hierarchy AC are also introduced by him.[11] According to Don Knuth
Don Knuth
the KMP algorithm was inspired by Cook's automata for recognizing concatenated palindromes in linear time.[12] Awards and honors[edit] 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
Royal Society of London
and Royal Society
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
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.[13] The Government of Ontario
Government of Ontario
appointed him to the Order of Ontario
Order of Ontario
in 2013, the highest honor in Ontario.[14] He has won the 2012 Gerhard Herzberg Canada
Gold Medal for Science and Engineering, the highest honor for scientist and engineers in Canada.[15] The Herzberg Medal is awarded by NSERC
for "both the sustained excellence and overall influence of research work conducted in Canada
in the natural sciences or engineering".[16] He was named an Officer of the Order of Canada
Order of Canada
in 2015.[17] Cook was granted the BBVA Foundation Frontiers of Knowledge Award 2015 in the Information and Communication Technologies category “for his important role in identifying what computers can and cannot solve efficiently,” in the words of the jury’s citation. His work, it continues, “has had a dramatic impact in all fields where complex computations are crucial.” Cook has supervised numerous MSc students, and 34 PhD students have completed their degrees under his supervision.[18] Personal life[edit] Cook currently lives with his wife in Toronto. They have two sons, Gordon and James.[19] He plays the violin and enjoys sailing. He is often called by his short name Steve Cook.

Professors Stephen A. Cook (right) with his friend Prof. Jan Krajíček (left) at the Fall school of Logic & Complexity in Prague, September 24, 2008

See also[edit]

List of pioneers in computer science


^ Stephen A. Cook, Turing Award
Turing Award
Winner ^ A Personal View of Computer Science
Computer Science
at Berkeley - Richard Karp ^ "The Complexity of Theorem Proving Procedures", PDF file of a scanned version ^ "The Complexity of Theorem Proving Procedures", PDF file of a retyped version ^ P vs. NP Archived October 14, 2013, at the Wayback Machine. problem on Millennium Prize Problems page - Clay Mathematics
Institute ^ P vs. NP Archived 2007-09-27 at the Wayback Machine. problem's official description by Stephen Cook
Stephen Cook
on Millennium Prize Problems ^ "Feasibly Constructive Proofs and the Propositional Calculus" on ACM ^ "The Relative Efficiency of Propositional Proof Systems" on JStore ^ "Logical Foundations of Proof Complexity"'s official page ^ ""Steve's class": origin of SC". Theoretical Computer Science
Computer Science
- Stack Exchange.  ^ "Who introduced the complexity class AC?". Theoretical Computer Science - Stack Exchange.  ^ "Twenty Questions for Donald Knuth".  ^ Stephen Cook
Stephen Cook
Archived 2009-01-23 at the Wayback Machine. on ACM Fellows ^ "25 Appointees Named to Ontario's Highest Honour". Ministry of Citizenship and Immigration.  ^ Emily, Chung (February 27, 2013). "Computer scientist wins Canada's top science prize". cbc.ca. Retrieved February 27, 2013.  ^ "Current Winner - 2012 - Stephen Cook".  ^ "Four Nova Scotians among Order of Canada
Order of Canada
honourees". The Chronicle-Herald, July 1, 2015. ^ Stephen Cook
Stephen Cook
at the Mathematics
Genealogy Project ^ "Stephen A. Cook - Home Page". 

External links[edit]

Home page of Stephen A. Cook ‘P versus NP’ and the Limits of Computation - Public lecture given by Stephen Cook
Stephen Cook
at the University of Toronto Oral history interview with Stephen Cook
Stephen Cook
at Charles Babbage Institute, University of Minnesota. Cook discussed his education at the University of Michigan
University of Michigan
and Harvard University
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
University of Toronto
in 1970 and the reception of his work on NP-completeness, leading up to his A.M. Turing Award. Stephen Arthur Cook at the Mathematics
Genealogy Project Stephen A. Cook at DBLP Bibliography Server

v t e

Fellows of the Royal Society
Royal Society
elected in 1998


Colin Atkinson David Barker Jean Beggs Harshad Bhadeshia David Keith Bowen Roger Cashmore Andrew Casson Thomas Cavalier-Smith David W. Clarke Enrico Coen Stephen Cook Peter Crane Richard Denton Raymond Dwek Charles Ellington Richard B. Flavell Ken Freeman Brian Greenwood J. Philip Grime David Hanna Geoffrey Hinton Steven Martin Raghunath Anant Mashelkar Yoshio Masui Ronald Charles Newman Mark Pepys Trevor Charles Platt Alan Plumb Richard J. Puddephatt Philip Ruffles Anthony Segal Ashoke Sen Jonathan Sprent James Staunton John Michael Taylor Robert K. Thomas Cheryll Tickle S. R. Srinivasa Varadhan Bernard Wood Brian S. Worthington


John E. Casida Elias James Corey Walter Kohn Oliver Smithies Rolf M. Zinkernagel

v t e

A. M. Turing Award
Turing Award


Alan Perlis (1966) Maurice Vincent Wilkes (1967) Richard Hamming
Richard Hamming
(1968) Marvin Minsky
Marvin Minsky


James H. Wilkinson (1970) John McCarthy (1971) Edsger W. Dijkstra
Edsger W. Dijkstra
(1972) Charles Bachman
Charles Bachman
(1973) Donald Knuth
Donald Knuth
(1974) Allen Newell / Herbert A. Simon
Herbert A. Simon
(1975) Michael O. Rabin
Michael O. Rabin
/ Dana Scott
Dana Scott
(1976) John Backus
John Backus
(1977) Robert W. Floyd (1978) Kenneth E. Iverson
Kenneth E. Iverson


Tony Hoare
Tony Hoare
(1980) Edgar F. Codd
Edgar F. Codd
(1981) Stephen Cook
Stephen Cook
(1982) Ken Thompson
Ken Thompson
/ Dennis Ritchie
Dennis Ritchie
(1983) Niklaus Wirth
Niklaus Wirth
(1984) Richard Karp
Richard Karp
(1985) John Hopcroft
John Hopcroft
/ Robert Tarjan
Robert Tarjan
(1986) John Cocke (1987) Ivan Sutherland
Ivan Sutherland
(1988) William Kahan
William Kahan


Fernando J. Corbató
Fernando J. Corbató
(1990) Robin Milner (1991) Butler Lampson (1992) Juris Hartmanis
Juris Hartmanis
/ Richard E. Stearns
Richard E. Stearns
(1993) Edward Feigenbaum
Edward Feigenbaum
/ Raj Reddy
Raj Reddy
(1994) Manuel Blum
Manuel Blum
(1995) Amir Pnueli
Amir Pnueli
(1996) Douglas Engelbart
Douglas Engelbart
(1997) Jim Gray (1998) Fred Brooks
Fred Brooks


Andrew Yao
Andrew Yao
(2000) Ole-Johan Dahl / Kristen Nygaard
Kristen Nygaard
(2001) Ron Rivest
Ron Rivest
/ Adi Shamir
Adi Shamir
/ Leonard Adleman
Leonard Adleman
(2002) Alan Kay
Alan Kay
(2003) Vint Cerf
Vint Cerf
/ Bob Kahn
Bob Kahn
(2004) Peter Naur
Peter Naur
(2005) Frances E. Allen
Frances E. Allen
(2006) Edmund M. Clarke
Edmund M. Clarke
/ E. Allen Emerson / Joseph Sifakis (2007) Barbara Liskov
Barbara Liskov
(2008) Charles P. Thacker
Charles P. Thacker


Leslie G. Valiant (2010) Judea Pearl
Judea Pearl
(2011) Shafi Goldwasser
Shafi Goldwasser
/ Silvio Micali
Silvio Micali
(2012) Leslie Lamport
Leslie Lamport
(2013) Michael Stonebraker
Michael Stonebraker
(2014) Martin Hellman / Whitfield Diffie
Whitfield Diffie
(2015) Tim Berners-Lee
Tim Berners-Lee
(2016) John L. Hennessy
John L. Hennessy
/ David Patterson (2017)

Authority control

WorldCat Identities VIAF: 38354675 LCCN: nr2003030022 ISNI: 0000 0000 8220 6950 GND: 140808973 SUDOC: 074089021 MGP: 14011 DBLP: c/StephenACook A