Stephen Arthur Cook

Stephen Arthur Cook was born on December 14, 1939 in Buffalo, NY. Cook’s father worked as a chemist for a subsidiary of Union Carbide, and was also an adjunct professor at SUNY Buffalo. His mother worked as a homemaker and also as an occasional English teacher at Erie Community College. When he was ten, Cook moved with his family to Clarence, NY, which was the home of Wilson Greatbatch, the inventor of the implantable pacemaker. As a teenager, Stephen developed an interest in electronics and worked forGreatcatch, who was then experimenting with transistor-based circuitry.

Cook entered the University of Michigan in 1957, majoring in science engineering. He was introduced to computer programming in a freshman course taught by Bernard Galler. With a fellow student he wrote a program to test Goldbach’s conjecture that every even integer greater than two is the sum of two primes. Stephen eventually changed his major to mathematics, and received his Bachelor’s degree in 1961. He subsequently entered graduate studies in the Mathematics Department at Harvard University, where he encountered influences that would shape the direction of his future research, including Michael Rabin’s early work on computational complexity, Alan Cobham’s characterization of polynomial time computable functions, and his supervisor Hao Wang’s investigations in automated theorem proving. Cook received his Ph.D. in 1966. His thesis, titled On the Minimum Computation time of Functions, addresses the intrinsic computational complexity of multiplication. One contribution of the thesis was an improvement of Andrei Toom’s multiplication algorithm, which is now known as Toom-Cook multiplication. This algorithm is still a subject of study and is of practical importance in high-precision arithmetic.

After graduating, he joined the Mathematics Department at the University of California, Berkeley, leaving there in 1970 to take the position of Associate Professor in Computer Science at the University of Toronto. A year later, Cook presented his seminal paper, “The complexity of theorem proving procedures,” at the 3rd Annual ACM Symposium on Theory of Computing [1]. This paper marked the introduction of the theory of NP-completeness, which henceforth occupied a central place in theoretical computer science. (Leonid Levin independently introduced NP-completeness in 1973.) It was also an early contribution to the theory of propositional proof complexity, an area in which Cook continued to do extensive research over the next 40 years.

The theory of NP-completeness provides a way to characterize the difficulty of computational problems with respect to the time, that is, the maximum number of computational steps required to solve a problem, as a function of input size. Cook’s paper addresses the fact that many problems which are difficult to solve in this sense have solutions which are easy to verify once they are found. In current terminology, problems which are easy to solve comprise the class P, while those which are easy to verify comprise the class NP. Cook showed that certain problems in NP, now known as NP-complete problems, are as hard to solve as any others in NP, in the sense that if any one of these problems is easy to solve, then all problems in NP are easy to solve. Cook’s paper also was the source of the celebrated and still unsolved P versus NP question, which asks whether there are indeed problems in NP which are not in P, that is, problems whose solutions are easily verified but are not easily solved. A simple example which elucidates the relationship between the classes P and NP is the popular Sudoku puzzle (see here).

Cook’s paper had an immediate impact. In 1972 Richard Karp published a paper in which he showed that twenty-one problems in combinatorics, optimization and graph theory which were believed to be computationally difficult were indeed NP-complete. Seven years later, Michael Garey and David Johnson published the book Computers and Intractability: A Guide to the Theory of NP-Completeness, which included a compendium of over three hundred problems which by then had been shown to be NP-compete. It would be hard to estimate how many problems have now been proved to be NP-complete, but they certainly number in the thousands. More significantly, the use of NP-completeness as a tool to understand computational difficulty spans virtually all areas of computer science.

The 1970 paper (“The complexity of theorem proving procedures”) introduced concepts and techniques which have had a lasting impact in various fields of computer science. In the paper, Cook introduces a canonical NP-complete problem, the satisfiability problem for Boolean formulas (SAT). The study of the SAT problem has become a field in its own right, and the development and use of specialized programs known as SAT-solvers has become an important practical approach to problems in areas such as verification and circuit design. In order to show that other problems are NP-complete, Cook developed the method of resource-bounded reducibility. This technique is an essential tool in computational complexity theory and is the foundation of complexity-based approaches to cryptographic security.

The impact of the P versus NP problem has extended beyond the field of computer science. In particular, it has been recognized as a mathematical problem of fundamental significance. In the year 2000, Fields Medalist Steve Smale listed the P versus NP problem as the third in his list of eighteen unsolved problems in mathematics for the 21st century. In the same year, the Clay Mathematics Institute announced the Millennium Prize Problems. In the words of the Institute, the prize was proposed “to record some of the most difficult problems with which mathematicians were grappling at the turn of the second millennium.’’ The P versus NP was included as one of these seven fundamental problems.

Cook has also made important contributions to areas of mathematical logic related to computational complexity. The paper “The relative efficiency of propositional proof systems,”[2] co-authored with his student Robert Reckhow, laid the foundations of propositional proof complexity. His 1975 paper, ``Feasibly constructive proofs and the propositional calculus’’ [3] introduces a logical system which characterizes feasible reasoning, and demonstrates how such reasoning is related to efficiency in propositional proof systems. He has also done significant work in areas including automata theory, parallel computation, program language semantics and verification, computational algebra, and computability and complexity in higher types.

Professor Cook’s work has received extensive recognition. He was awarded the ACM Turing Award in 1982. He is a fellow of the Royal Society of Canada and the Royal Society of London, and is a member of the National Academy of Sciences (U.S.), the American Academy of Arts and Sciences, and the Gottingen Academy of Sciences. He has been a recipient of the Canada Council Izaak Walton Killam Memorial Prize in 1997, the CRM-Fields Prize in 1999, the Royal Society of Canada John L. Synge Award in 2006, the NSERC Award of Excellence in 2007, and the Czech Academy of Sciences Bernard Bolzano Medal in2008. He was an NSERC Steacie Fellow in 1978-79 and was awarded a Killam Research Fellowship in 1982-83.

In 1985, Stephen Cook was promoted to the position of University Professor at the University of Toronto, and now holds the position of Distinguished University Professor in the Computer Science and Mathematics Departments. Over the course of his career he has mentored over thirty Ph.D. students, and continues to be active in teaching, research and graduate supervision. His book, Logical Foundations of Proof Complexity, co-authored with Phuong Nguyen, appeared in 2010. He currently lives in Toronto with his wife Linda, and has two sons. He is an avid sailor and a long-time member of the Royal Canadian Yacht Club.

Enduring Links of Interest

• Clay Foundation Millenium Problem Prize page on the P vs NP problem
• Oral history interview with Stephen A. Cook at the Charles Babbage Institute
• Stephen A. Cook at the Mathematics Genealogy Project

Author: Bruce Kapron