Stephen Cook

Last updated

Stephen Cook

OC OOnt
Prof.Cook.jpg
Cook in 2008
Born
Stephen Arthur Cook

(1939-12-14) December 14, 1939 (age 84)
Buffalo, New York
Alma mater Harvard University
University of Michigan
Known for NP-completeness
Propositional proof 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 Cook OC OOnt (born December 14, 1939) is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.

Contents

He is considered one of the forefathers of computational complexity theory.

Biography

Cook in 1968 Stephen A. Cook 1968 (enlarged portion).jpg
Cook in 1968

Cook received his bachelor's degree in 1961 from the University of Michigan, and his master's degree and PhD from Harvard University, respectively in 1962 and 1966, from the Mathematics Department. [2] 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 electrical engineering and computer sciences 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." [3] Cook joined the faculty of the 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

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 of polynomial-time reduction (also known as 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) that 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 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 that 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. [10] The definition of the complexity class AC0 and its hierarchy AC are also introduced by him. [11]

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

Awards and honors

Cook was awarded an NSERC E.W.R. Steacie Memorial 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. He is a corresponding member of the Göttingen Academy of Sciences and Humanities.

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. [13] He was selected by the Association for Symbolic Logic to give the Gödel Lecture in 1999. [14]

The Government of Ontario appointed him to the Order of Ontario in 2013, the highest honor in Ontario. [15] He has won the 2012 Gerhard Herzberg Canada Gold Medal for Science and Engineering, the highest honor for scientists and engineers in Canada. [16] 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". [17] He was named an Officer of the Order of Canada in 2015. [18]

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 36 PhD students have completed their degrees under his supervision. [1]

Personal life

Cook lives with his wife in Toronto. They have two sons, one of whom is Olympic sailor Gordon Cook. [19]

See also

Related Research Articles

The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In computability theory, the Church–Turing thesis is a thesis about the nature of computable functions. It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine. The thesis is named after American mathematician Alonzo Church and the British mathematician Alan Turing. Before the precise definition of computable function, mathematicians often used the informal term effectively calculable to describe functions that are computable by paper-and-pencil methods. In the 1930s, several independent attempts were made to formalize the notion of computability:

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

<span class="mw-page-title-main">Theory of computation</span> Academic subfield of computer science

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree. The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n2 time but not n time, where n is the input length.

<span class="mw-page-title-main">Richard M. Karp</span> American mathematician

Richard Manning Karp is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.

<span class="mw-page-title-main">Juris Hartmanis</span> American computer scientist (1928–2022)

Juris Hartmanis was a Latvian-born American computer scientist and computational theorist who, with Richard E. Stearns, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory".

<span class="mw-page-title-main">Leonid Levin</span> Soviet-American mathematician

Leonid Anatolievich Levin is a Soviet-American mathematician and computer scientist.

<span class="mw-page-title-main">Complexity class</span> Set of problems in computational complexity theory

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.

In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem.

<span class="mw-page-title-main">Shafi Goldwasser</span> Israeli American computer scientist

Shafrira Goldwasser is an Israeli-American computer scientist and winner of the Turing Award in 2012. She is the RSA Professor of Electrical Engineering and Computer Science at Massachusetts Institute of Technology; a professor of mathematical sciences at the Weizmann Institute of Science, Israel; the director of the Simons Institute for the Theory of Computing at the University of California, Berkeley; and co-founder and chief scientist of Duality Technologies.

<span class="mw-page-title-main">Russell Impagliazzo</span> American computer scientist

Russell Graham Impagliazzo is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory.

In logic and theoretical computer science, and specifically proof theory and computational complexity theory, proof complexity is the field aiming to understand and analyse the computational resources that are required to prove or refute statements. Research in proof complexity is predominantly concerned with proving proof-length lower and upper bounds in various propositional proof systems. For example, among the major challenges of proof complexity is showing that the Frege system, the usual propositional calculus, does not admit polynomial-size proofs of all tautologies. Here the size of the proof is simply the number of symbols in it, and a proof is said to be of polynomial size if it is polynomial in the size of the tautology it proves.

In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity.

Aleksandr Aleksandrovich Razborov, sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist. He is Andrew McLeish Distinguished Service Professor at the University of Chicago.

<span class="mw-page-title-main">Michael Sipser</span> American theoretical computer scientist (born 1954)

Michael Fredric Sipser is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the Dean of Science at the Massachusetts Institute of Technology.

<span class="mw-page-title-main">NP-completeness</span> Complexity class

In computational complexity theory, a problem is NP-complete when:

  1. It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".
  2. When the answer is "yes", this can be demonstrated through the existence of a short solution.
  3. The correctness of each solution can be verified quickly and a brute-force search algorithm can find a solution by trying all possible solutions.
  4. The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.
<span class="mw-page-title-main">Toniann Pitassi</span> Canadian-American computer scientist

Toniann Pitassi is a Canadian-American mathematician and computer scientist specializing in computational complexity theory. She is currently Jeffrey L. and Brenda Bleustein Professor of Engineering at Columbia University and was Bell Research Chair at the University of Toronto.

Bounded arithmetic is a collective name for a family of weak subtheories of Peano arithmetic. Such theories are typically obtained by requiring that quantifiers be bounded in the induction axiom or equivalent postulates. The main purpose is to characterize one or another class of computational complexity in the sense that a function is provably total if and only if it belongs to a given complexity class. Further, theories of bounded arithmetic present uniform counterparts to standard propositional proof systems such as Frege system and are, in particular, useful for constructing polynomial-size proofs in these systems. The characterization of standard complexity classes and correspondence to propositional proof systems allows to interpret theories of bounded arithmetic as formal systems capturing various levels of feasible reasoning.

References

  1. 1 2 Stephen Cook at the Mathematics Genealogy Project
  2. ↑ Kapron, Bruce. "Stephen Arthur Cook". A. M. Turing Award. Retrieved October 23, 2018.
  3. ↑ Richard Karp (2003). "A Personal View of Computer Science at Berkeley". University of California Berkeley. Retrieved February 12, 2023.
  4. ↑ Stephen Cook (1971), The Complexity of Theorem Proving Procedures (PDF)– via University of Toronto
    Stephen A. Cook (2009) [1971]. "The Complexity of Theorem-Proving Procedures" . Retrieved February 12, 2023.
  5. ↑ P vs. NP Archived October 14, 2013, at the Wayback Machine problem on Millennium Prize Problems page – Clay Mathematics Institute
  6. ↑ P vs. NP Archived September 27, 2007, at the Wayback Machine problem's official description by Stephen Cook on Millennium Prize Problems
  7. ↑ Cook, Stephen A. (May 5, 1975). "Feasibly constructive proofs and the propositional calculus (Preliminary Version)". Proceedings of seventh annual ACM symposium on Theory of computing - STOC '75. New York: Association for Computing Machinery. pp. 83–97. doi:10.1145/800116.803756. ISBN   978-1-4503-7419-4. S2CID   13309619.
  8. ↑ Cook, Stephen A.; Reckhow, Robert A. (1979). "The Relative Efficiency of Propositional Proof Systems". The Journal of Symbolic Logic. 44 (1): 36–50. doi:10.2307/2273702. ISSN   0022-4812. JSTOR   2273702. S2CID   2187041.
  9. ↑ "Logical Foundations of Proof Complexity"'s official page
  10. ↑ ""Steve's class": origin of SC". Theoretical Computer Science – Stack Exchange.
  11. ↑ "Who introduced the complexity class AC?". Theoretical Computer Science – Stack Exchange.
  12. ↑ "Twenty Questions for Donald Knuth".
  13. ↑ Association for Computing Machinery. "Stephen A Cook". awards.acm.org. Retrieved February 12, 2023.
  14. ↑ "Gödel Lecturers – Association for Symbolic Logic" . Retrieved November 8, 2021.
  15. ↑ "25 Appointees Named to Ontario's Highest Honour". Ministry of Citizenship and Immigration.
  16. ↑ Emily, Chung (February 27, 2013). "Computer scientist wins Canada's top science prize". cbc.ca. Retrieved February 27, 2013.
  17. ↑ "Current Winner – 2012 – Stephen Cook". June 28, 2016.
  18. ↑ "SaltWire | Halifax". www.saltwire.com. Retrieved February 12, 2023.
  19. ↑ "Stephen A. Cook – Home Page".
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.