Stephen Cook
Encyclopedia
Stephen Arthur Cook 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.
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." 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.
.
During his PhD, Cook worked on complexity of functions, mainly on multiplication. He received his PhD in 1966. A few years later, in his seminal 1971 paper "The Complexity of Theorem Proving Procedures", Cook formalized the notions of polynomial-time reduction
(a.k.a. Cook reduction) and NP-complete
ness, 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
.
In 1982, Cook received the prestigious Turing award
for his contributions to complexity theory. His citation reads:
In his "Feasibly Constructive Proofs and the Propositional Calculus" 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", 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".
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.
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.
Cook has supervised numerous MSc students, and 30 PhD students have completed their degrees under his supervision.
. He plays the violin
and enjoys sailing
.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and mathematician
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
who has made major contributions to the fields of complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
and proof complexity
Proof complexity
In computer science, proof complexity is a measure of efficiency of automated theorem proving methods that is based on the size of the proofs they produce. The methods for proving contradiction in propositional logic are the most analyzed...
. He is currently a University Professor at the University of Toronto
University of Toronto
The University of Toronto is a public research university in Toronto, Ontario, Canada, situated on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution of higher learning in Upper Canada...
, Department of Computer Science and Department of Mathematics.
Biography
Cook received his Bachelor's degreeBachelor's degree
A bachelor's degree is usually an academic degree awarded for an undergraduate course or major that generally lasts for three or four years, but can range anywhere from two to six years depending on the region of the world...
in 1961 from the University of Michigan
University of Michigan
The University of Michigan is a public research university located in Ann Arbor, Michigan in the United States. It is the state's oldest university and the flagship campus of the University of Michigan...
, and his Master's degree
Master's degree
A master's is an academic degree granted to individuals who have undergone study demonstrating a mastery or high-order overview of a specific field of study or area of professional practice...
and Ph.D.
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
from Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
, respectively in 1962 and 1966. He joined the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
, 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
Richard Karp
Richard Manning Karp is a computer scientist and computational theorist at the University of California, Berkeley, notable for 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...
said that, "It is to our everlasting shame that we were unable to persuade the math department to give him tenure." Cook joined the faculty of University of Toronto
University of Toronto
The University of Toronto is a public research university in Toronto, Ontario, Canada, situated on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution of higher learning in Upper Canada...
, Computer Science and Mathematics Departments in 1970 as an Associate Professor, where he was promoted to Professor in 1975 and University Professor in 1985.
Research
Cook is considered one of the forefathers of computational complexity theoryComputational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
.
During his PhD, Cook worked on complexity of functions, mainly on multiplication. He received his PhD in 1966. A few years later, in his seminal 1971 paper "The Complexity of Theorem Proving Procedures", Cook formalized the notions of polynomial-time reduction
Polynomial-time reduction
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. If it is a many-one reduction, it is called a polynomial-time many-one reduction, polynomial transformation, or Karp reduction...
(a.k.a. Cook reduction) and NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
ness, and proved the existence of an NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problem by showing that the Boolean satisfiability problem
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
(usually known as SAT) is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
. This theorem was proven independently by Leonid Levin
Leonid Levin
-External links:* at Boston University....
in the Soviet Union
Soviet Union
The Soviet Union , officially the Union of Soviet Socialist Republics , was a constitutionally socialist state that existed in Eurasia between 1922 and 1991....
, 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
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, 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
Millennium Prize Problems
The Millennium Prize Problems are seven problems in mathematics that were stated by the Clay Mathematics Institute in 2000. As of September 2011, six of the problems remain unsolved. A correct solution to any of the problems results in a US$1,000,000 prize being awarded by the institute...
.
In 1982, Cook received the prestigious Turing award
Turing Award
The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...
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" paper published in 1975, he introduced the equational theory PV
PV
PV may refer to:In computing:* Page view, a metric in web analytics* Semaphores, from P and V operations in semaphores restricting processes in a shared environment...
(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", in which they formalized the notions of p-simulation and efficient propositional proof system
Propositional proof system
In propositional calculus and proof complexity a propositional proof system , also called a Cook–Reckhow propositional proof system, is system for proving classical propositional tautologies.- Mathematical definition :...
, which started an area now called propositional proof complexity
Proof complexity
In computer science, proof complexity is a measure of efficiency of automated theorem proving methods that is based on the size of the proofs they produce. The methods for proving contradiction in propositional logic are the most analyzed...
. They proved that the existence of a proof system in which every true formula has a short proof is equivalent to NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
= coNP. Cook co-authored a book with his student Phuong The Nguyen in this area titled "Logical Foundations of Proof Complexity".
His main research areas are complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
and proof complexity
Proof complexity
In computer science, proof complexity is a measure of efficiency of automated theorem proving methods that is based on the size of the proofs they produce. The methods for proving contradiction in propositional logic are the most analyzed...
, with excursions into programming language semantics, parallel computation, and artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
. 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 prizeCRM-Fields-PIMS prize
The CRM-Fields prize was given annually by the Centre de recherches mathématiques and the Fields Institute from 1994 to 2005. From 2006the Pacific Institute for the Mathematical Sciences joined the other two institutes awarding the prize, making the CRM-Fields-PIMS Prize.The prize is given for...
in 1999. He has won John L. Synge Award
John L. Synge Award
John L. Synge Award is an award by the Royal Society of Canada for outstanding research in any branch of the mathematical sciences. It was created in 1986 and is given at irregular intervals. The award is named in honor of John Lighton Synge.- Winners :...
and Bernard Bolzano Medal, and is a fellow of the Royal Society of London and Royal Society of Canada
Royal Society of Canada
The Royal Society of Canada , may also operate under the more descriptive name RSC: The Academies of Arts, Humanities and Sciences of Canada , is the oldest association of scientists and scholars in Canada...
. Cook was elected to membership in the National Academy of Sciences
United States National Academy of Sciences
The National Academy of Sciences is a corporation in the United States whose members serve pro bono as "advisers to the nation on science, engineering, and medicine." As a national academy, new members of the organization are elected annually by current members, based on their distinguished and...
(United States
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
) and the American Academy of Arts and Sciences
American Academy of Arts and Sciences
The American Academy of Arts and Sciences is an independent policy research center that conducts multidisciplinary studies of complex and emerging problems. The Academy’s elected members are leaders in the academic disciplines, the arts, business, and public affairs.James Bowdoin, John Adams, and...
. Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
honored him as a Fellow of ACM
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
in 2008 for his
fundamental contributions to the theory of computational complexity.
Cook has supervised numerous MSc students, and 30 PhD students have completed their degrees under his supervision.
Personal life
Cook has two children and currently lives with his wife in TorontoToronto
Toronto is the provincial capital of Ontario and the largest city in Canada. It is located in Southern Ontario on the northwestern shore of Lake Ontario. A relatively modern city, Toronto's history dates back to the late-18th century, when its land was first purchased by the British monarchy from...
. He plays the violin
Violin
The violin is a string instrument, usually with four strings tuned in perfect fifths. It is the smallest, highest-pitched member of the violin family of string instruments, which includes the viola and cello....
and enjoys sailing
Sailing
Sailing is the propulsion of a vehicle and the control of its movement with large foils called sails. By changing the rigging, rudder, and sometimes the keel or centre board, a sailor manages the force of the wind on the sails in order to move the boat relative to its surrounding medium and...
.
External links
- Home page of Stephen A. Cook
- Oral history interview with Stephen Cook at Charles Babbage InstituteCharles Babbage InstituteThe Charles Babbage Institute is a research center at the University of Minnesota specializing in the history of information technology, particularly the history since 1935 of digital computing, programming/software, and computer networking....
, 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 DBLPDBLPDBLP is a computer science bibliography website hosted at Universität Trier, in Germany. It was originally a database and logic programming bibliography site, and has existed at least since the 1980s. DBLP listed more than 1.3 million articles on computer science in January 2010...