Stephen Cook
   HOME

TheInfoList



OR:

Stephen Arthur Cook (born December 14, 1939) is an American-Canadian
computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...
and mathematician who has made significant contributions to the fields of complexity theory and
proof complexity 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. ...
. He is a university professor emeritus at the
University of Toronto The University of Toronto (UToronto or U of T) is a public university, public research university whose main campus is located on the grounds that surround Queen's Park (Toronto), Queen's Park in Toronto, Ontario, Canada. It was founded by ...
, Department of Computer Science and Department of Mathematics. He is considered one of the forefathers of
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
.


Biography

Cook received his
bachelor's degree A bachelor's degree (from Medieval Latin ''baccalaureus'') or baccalaureate (from Modern Latin ''baccalaureatus'') is an undergraduate degree awarded by colleges and universities upon completion of a course of study lasting three to six years ...
in 1961 from the
University of Michigan The University of Michigan (U-M, U of M, or Michigan) is a public university, public research university in Ann Arbor, Michigan, United States. Founded in 1817, it is the oldest institution of higher education in the state. The University of Mi ...
, and his master's degree and PhD from
Harvard University Harvard University is a Private university, private Ivy League research university in Cambridge, Massachusetts, United States. Founded in 1636 and named for its first benefactor, the History of the Puritans in North America, Puritan clergyma ...
, respectively in 1962 and 1966, from the Mathematics Department. He joined the
University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California), is a Public university, public Land-grant university, land-grant research university in Berkeley, California, United States. Founded in 1868 and named after t ...
, 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 The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in the fi ...
winner and Berkeley professor
Richard Karp Richard Manning Karp (born January 3, 1935) 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 Turin ...
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 the
University of Toronto The University of Toronto (UToronto or U of T) is a public university, public research university whose main campus is located on the grounds that surround Queen's Park (Toronto), Queen's Park in Toronto, Ontario, Canada. It was founded by ...
, 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", Cook formalized the notions of
polynomial-time reduction In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming ...
(also known as
Cook reduction In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine that decides problem A given an oracle for B (Rogers 1967, Soare 1987) in finitely many steps. It can be understood as an algorithm ...
) and
NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
ness, and proved the existence of an
NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
problem by showing that the
Boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) asks whether there exists an Interpretation (logic), interpretation that Satisf ...
(usually known as SAT) is
NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
. This theorem was proven independently by
Leonid Levin Leonid Anatolievich Levin ( ; ; ; born November 2, 1948) is a Soviet-American mathematician and computer scientist. He is known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity, fou ...
in the
Soviet Union The Union of Soviet Socialist Republics. (USSR), commonly known as the Soviet Union, was a List of former transcontinental countries#Since 1700, transcontinental country that spanned much of Eurasia from 1922 until Dissolution of the Soviet ...
, 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 In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
, 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 The Millennium Prize Problems are seven well-known complex mathematics, mathematical problems selected by the Clay Mathematics Institute in 2000. The Clay Institute has pledged a US $1 million prize for the first correct solution to each problem ...
. 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" 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 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. ...
. 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 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. ...
, with excursions into
programming language semantics In programming language theory, semantics is the rigorous mathematical study of the meaning of programming languages. Semantics assigns computational meaning to valid strings in a programming language syntax. It is closely related to, and ofte ...
, parallel computation, and
artificial intelligence Artificial intelligence (AI) is the capability of computer, computational systems to perform tasks typically associated with human intelligence, such as learning, reasoning, problem-solving, perception, and decision-making. It is a field of re ...
. 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 system In mathematical logic, a proof calculus or a proof system is built to prove statements. Overview A proof system includes the components: * Formal language: The set ''L'' of formulas admitted by the system, for example, propositional logic or fir ...
s.


Some other contributions

He named the complexity class NC after Nick Pippenger. The complexity class SC is named after him. The definition of the complexity class AC0 and its hierarchy AC are also introduced by him. According to Don Knuth the KMP algorithm was inspired by Cook's automata for recognizing concatenated palindromes in
linear time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
.


Awards and honors

Cook was awarded an
NSERC The Natural Sciences and Engineering Research Council of Canada (NSERC; , CRSNG) is the major federal agency responsible for funding natural sciences and engineering research in Canada. NSERC directly funds university professors and students as ...
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 of the
Czech Academy of Sciences The Czech Academy of Sciences (abbr. CAS, , abbr. AV ČR) was established in 1992 by the Czech National Council as the Czech successor of the former Czechoslovak Academy of Sciences and its tradition goes back to the Royal Bohemian Society of Sc ...
(2008), and is a fellow of the
Royal Society of London The Royal Society, formally The Royal Society of London for Improving Natural Knowledge, is a learned society and the United Kingdom's national academy of sciences. The society fulfils a number of roles: promoting science and its benefits, r ...
and
Royal Society of Canada The Royal Society of Canada (RSC; , SRC), also known as the Academies of Arts, Humanities, and Sciences of Canada (French: ''Académies des arts, des lettres et des sciences du Canada''), is the senior national, bilingual council of distinguishe ...
. Cook was elected to membership in the
National Academy of Sciences The National Academy of Sciences (NAS) is a United States nonprofit, NGO, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the ...
(United States) and the
American Academy of Arts and Sciences The American Academy of Arts and Sciences (The Academy) is one of the oldest learned societies in the United States. It was founded in 1780 during the American Revolution by John Adams, John Hancock, James Bowdoin, Andrew Oliver, and other ...
. He is a corresponding member of the
Göttingen Academy of Sciences and Humanities The Göttingen Academy of Sciences (name since 2023 : )Note that the German ''Wissenschaft'' has a wider meaning than the English "Science", and includes Social sciences and Humanities. is the oldest continuously existing institution among the eig ...
. Cook won the ACM
Turing Award The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in the fi ...
in 1982.
Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional membe ...
honored him as a Fellow of ACM in 2008 for his ''fundamental contributions to the theory of computational complexity''. He was selected by the Association for Symbolic Logic to give the
Gödel Lecture The Gödel Lecture is an honor in mathematical logic given by the Association for Symbolic Logic, associated with an annual lecture at the association's general meeting. The award is named after Kurt Gödel and has been given annually since 1990. ...
in 1999. The
Government of Ontario The Government of Ontario () is the body responsible for the administration of the Provinces and territories of Canada, Canadian province of Ontario. The term ''Government of Ontario'' refers specifically to the executive—political Minister ...
appointed him to the
Order of Ontario The Order of Ontario is a civilian honour for merit in the Canadian province of Ontario. Instituted in 1986 by Lieutenant Governor of Ontario, Lieutenant Governor Lincoln Alexander, on the Advice (constitutional), advice of the Executive Council ...
in 2013, the highest honor in
Ontario Ontario is the southernmost Provinces and territories of Canada, province of Canada. Located in Central Canada, Ontario is the Population of Canada by province and territory, country's most populous province. As of the 2021 Canadian census, it ...
. He has won the 2012 Gerhard Herzberg Canada Gold Medal for Science and Engineering, the highest honor for scientists and engineers in Canada. The Herzberg Medal is awarded by
NSERC The Natural Sciences and Engineering Research Council of Canada (NSERC; , CRSNG) is the major federal agency responsible for funding natural sciences and engineering research in Canada. NSERC directly funds university professors and students as ...
for "both the sustained excellence and overall influence of research work conducted in Canada in the natural sciences or engineering". He was named an
Officer of the Order of Canada The Order of Canada () is a Canadian national order and the second-highest honour for merit in the system of orders, decorations, and medals of Canada, after the Order of Merit. To coincide with the centennial of Canadian Confederation, the ...
in 2015. 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.


Personal life

Cook lives with his wife in
Toronto Toronto ( , locally pronounced or ) is the List of the largest municipalities in Canada by population, most populous city in Canada. It is the capital city of the Provinces and territories of Canada, Canadian province of Ontario. With a p ...
. They have two sons, one of whom is Olympic sailor Gordon Cook.


See also

*
List of pioneers in computer science This is a list of people who made transformative breakthroughs in the creation, development and imagining of what computers could do. Pioneers ~ Items marked with a tilde are circa dates. See also * Computer Pioneer Award * IEEE John von ...


References


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 The IT History Society (ITHS) is an organization that supports the history and scholarship of information technology by encouraging, fostering, and facilitating archival and historical research. Formerly known as the Charles Babbage Foundation, ...
, 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. * * {{DEFAULTSORT:Cook, Stephen Living people 1939 births Members of the United States National Academy of Sciences Members of the Order of Ontario Turing Award laureates Fellows of the Royal Society Fellows of the Royal Society of Canada 2008 fellows of the Association for Computing Machinery Academic staff of the University of Toronto University of Michigan alumni Harvard Graduate School of Arts and Sciences alumni University of California, Berkeley College of Letters and Science faculty American emigrants to Canada Officers of the Order of Canada American theoretical computer scientists Canadian theoretical computer scientists