Image

(born December 14, 1939)

Stephen Cook is among a short list of mathematics researchers whose ideas have spawned new fields of inquiry for current and future generations. A professor of Computer Science and Mathematics at the University of Toronto, Dr. Cook is the 2012 winner of the Natural Sciences and Engineering Research Council’s Herzberg Medal.

Image

Stephen Cook is the winner of the 1982 A.M. Turing Award, the highest honour in computer science, for his “advancement of our understanding of the complexity of computation in a significant and profound way.”

In addition to celebrated contributions to complexity theory, Dr. Cook has made fundamental contributions to computational theory, algorithm design, programming languages and mathematical logic, and his still-growing body of work is likely to be cited for many decades to come. His work has made an impact on various areas of mathematics and computation, and a contribution to many other fields of research.

Image

Cook earned a bachelor’s degree (1961) in computer science from the University of Michigan and a master’s degree (1962) and doctorate (1966) in computer science from Harvard University. After leaving Harvard, Cook joined the faculty at the University of California, Berkeley. In 1970 Cook moved to the University of Toronto, where in 1985 he was named a University Professor.In 1971 Cook published “The Complexity of Theorem Proving Procedures,” a seminal paper that laid the foundations for the theory of NP-complete problems—problems for which no efficient solution algorithm is known. The field remains one of the most important in computer science.Cook was elected to the Royal Society of London, the Royal Society of Canada, the U.S. National Academy of Sciences, and the American Academy of Arts and Sciences.

Image

Research

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

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-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.

In 1982, Cook received the prestigious Turing award for his contributions to complexity theory.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.

Awards and honours

Cook was awarded a Steacie 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. Association for Computing Machinery honored him as a Fellow of ACM in 2008 for his fundamental contributions to the theory of computational complexity. He was awarded the ACM Turing Award in 1982. He was appointed to the Order of Ontario in 2013. Cook was awarded the 2012 Gerhard Herzberg Canada Gold Medal for Science and Engineering. 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.

Image

Advertisements