Stephen Cook | |
|---|---|
 Cook in 2008 | |
| Born | Stephen Arthur Cook (1939-12-14)December 14, 1939 (age 85) Buffalo, New York |
| Education | University of Michigan (BA) Harvard University (MA,PhD) |
| Known for | NP-completeness Propositionalproof complexity Cook–Levin theorem |
| Awards | |
| Scientific career | |
| Fields | Computer Science |
| Institutions | University of Toronto University of California, Berkeley |
| Thesis | On the Minimum Computation Time of Functions (1966) |
| Doctoral advisor | Hao Wang |
| Doctoral students | Mark Braverman[1] Toniann Pitassi Walter Savitch Arvind Gupta Anna Lubiw |
Stephen Arthur CookOC OOnt (born December 14, 1939) is an American-Canadiancomputer scientist and mathematician who has made significant contributions to the fields ofcomplexity theory andproof complexity. He is a university professor emeritus at theUniversity of Toronto,Department of Computer Science andDepartment of Mathematics.
He is considered one of the forefathers ofcomputational complexity theory.
.jpg)
Cook received hisbachelor's degree in 1961 from theUniversity of Michigan, and his master's degree and PhD fromHarvard University, respectively in 1962 and 1966, from the Mathematics Department.[2] He joined theUniversity 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 electrical engineering and computer sciences department, fellowTuring Award winner and Berkeley professorRichard Karp said that, "It is to our everlasting shame that we were unable to persuade the math department to give him tenure."[3] Cook joined the faculty of theUniversity of Toronto,Computer Science andMathematics Departments in 1970 as an associate professor, where he was promoted to professor in 1975 andDistinguished Professor in 1985.
During his PhD, Cook worked on complexity of functions, mainly on multiplication. In his seminal 1971 paper "The Complexity of Theorem Proving Procedures",[4] Cook formalized the notions ofpolynomial-time reduction (also known asCook reduction) andNP-completeness, and proved the existence of anNP-complete problem by showing that theBoolean satisfiability problem (usually known as SAT) isNP-complete. This theorem was proven independently byLeonid Levin in theSoviet Union, and has thus been given the namethe Cook–Levin theorem. The paper also formulated the most famous problem in computer science, theP 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) that cannot be solved by efficient algorithms, i.e., P is not equal to NP. This conjecture has generated a great deal of research incomputational 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 famousMillennium Prize Problems.[5][6]
In 1982, Cook received the 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 studentRobert A. Reckhow, "The Relative Efficiency of Propositional Proof Systems",[8] in which they formalized the notions ofp-simulation and efficientpropositional proof system, which started an area now called propositionalproof complexity. They proved that the existence of a proof system in which every true formula has a short proof is equivalent toNP =coNP. Cook co-authored a book with his studentPhuong The Nguyen in this area titled "Logical Foundations of Proof Complexity".[9]
His main research areas arecomplexity theory andproof complexity, with excursions intoprogramming language semantics,parallel computation, andartificial intelligence. Other areas that he has contributed to includebounded arithmetic, boundedreverse mathematics,complexity of higher type functions,complexity of analysis, and lower bounds in propositionalproof systems.
He named the complexity classNC afterNick Pippenger. The complexity classSC is named after him.[10] The definition of the complexity classAC0 and its hierarchyAC are also introduced by him.[11]
According toDon Knuth theKMP algorithm was inspired by Cook's automata for recognizing concatenated palindromes inlinear time.[12]
Cook was awarded anNSERC E.W.R. Steacie Memorial Fellowship in 1977, a Killam Research Fellowship in 1982, and received theCRM-Fields-PIMS prize in 1999. He has wonJohn L. Synge Award andBernard Bolzano Medal of theCzech Academy of Sciences (2008),[13] and is a fellow of theRoyal Society of London andRoyal Society of Canada. Cook was elected to membership in theNational Academy of Sciences (United States) and theAmerican Academy of Arts and Sciences. He is a corresponding member of theGöttingen Academy of Sciences and Humanities.
Cook won the ACMTuring Award in 1982.Association for Computing Machinery honored him as a Fellow ofACM in 2008 for hisfundamental contributions to the theory of computational complexity.[14]He was selected by theAssociation for Symbolic Logic to give theGödel Lecture in 1999.[15]
TheGovernment of Ontario appointed him to theOrder of Ontario in 2013, the highest honor inOntario.[16] He has won the 2012Gerhard Herzberg Canada Gold Medal for Science and Engineering, the highest honor for scientists and engineers in Canada.[17] The Herzberg Medal is awarded byNSERC for "both the sustained excellence and overall influence of research work conducted in Canada in the natural sciences or engineering".[18] He was named anOfficer of the Order of Canada in 2015.[19][20]
Cook was granted theBBVA 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 36 PhD students have completed their degrees under his supervision.[1]
Cook lives with his wife inToronto. They have two sons, one of whom is Olympic sailorGordon Cook.[21]
