Stephen Arthur Cook OC OOnt was born on December 14, 1939. He is an American-Canadian computer scientist and mathematician who has made important contributions to the fields of complexity theory and proof complexity. He is a retired university professor at the University of Toronto, where he worked in the Department of Computer Science and the Department of Mathematics.

He is seen as one of the early pioneers of computational complexity theory. He received the 1982 ACM Turing Award.

Biography

Cook earned his bachelor's degree in 1961 from the University of Michigan. He later received his master's degree and PhD from Harvard University in 1962 and 1966, both from the Mathematics Department. In 1966, he began working at the University of California, Berkeley, as an assistant professor in the mathematics department. He remained there until 1970, when he was not given a permanent position. During a speech celebrating the 30th anniversary of the Berkeley electrical engineering and computer sciences department, Richard Karp, another Turing Award winner and a professor at Berkeley, said, "It is to our everlasting shame that we were unable to persuade the math department to give him tenure." Cook then joined the University of Toronto's Computer Science and Mathematics Departments in 1970 as an associate professor. He was promoted to professor in 1975 and became a Distinguished Professor in 1985.

Research

During his PhD, Cook studied the difficulty of solving certain mathematical problems, especially multiplication. In his important 1971 paper titled "The Complexity of Theorem Proving Procedures," Cook introduced the idea of polynomial-time reduction (also called Cook reduction) and NP-completeness. He showed that the Boolean satisfiability problem (SAT) is NP-complete. This result was also independently proven by Leonid Levin in the Soviet Union, and the discovery is now called the Cook–Levin theorem. The paper also introduced the famous P vs. NP problem. This question asks whether every problem that can be quickly checked for a correct answer can also be quickly solved. Since many such problems exist in daily life, answering this question positively could have major practical and philosophical effects.

Cook believes that some problems with easily checkable answers cannot be solved efficiently, meaning P is not equal to NP. This belief has led to much research in computational complexity theory, which has helped scientists better understand the difficulty of solving problems and what can be done quickly. However, the question remains unanswered and is one of the seven Millennium Prize Problems.

In 1982, Cook received the Turing Award for his work in complexity theory. In his 1975 paper, "Feasibly Constructive Proofs and the Propositional Calculus," he created the equational theory PV to describe proofs using only efficient concepts. In 1979, he and his student Robert A. Reckhow wrote a paper titled "The Relative Efficiency of Propositional Proof Systems," where they introduced the ideas of p-simulation and efficient propositional proof systems. This work started a field now called propositional proof complexity. They showed that having a proof system where every true statement has a short proof is the same as NP being equal to coNP. Cook also co-authored a book with his student Phuong The Nguyen on the topic of "Logical Foundations of Proof Complexity."

Cook’s main research areas include complexity theory and proof complexity, with some work in programming language semantics, parallel computation, and artificial intelligence. He has also contributed to fields like bounded arithmetic, bounded reverse mathematics, complexity of higher type functions, complexity of analysis, and lower bounds in propositional proof systems.

Cook named the complexity class NC after Nick Pippenger. The complexity class SC is named after him. He also defined the complexity class AC and its hierarchy.

According to Don Knuth, the KMP algorithm was inspired by Cook’s work on machines that can recognize palindromes joined together in linear time.

Awards and honors

In 1977, Cook was given an NSERC E.W.R. Steacie Memorial Fellowship. In 1982, he received a Killam Research Fellowship and also won the ACM Turing Award. In 1999, he was honored with the CRM-Fields-PIMS prize. Cook has also received the John L. Synge Award and the Bernard Bolzano Medal from the Czech Academy of Sciences in 2008. He is a member of the Royal Society of London and the Royal Society of Canada. Cook was elected to the National Academy of Sciences in the United States and the American Academy of Arts and Sciences. He is also a corresponding member of the Göttingen Academy of Sciences and Humanities.

In 2008, the Association for Computing Machinery recognized Cook as a Fellow of ACM for his important work in the theory of computational complexity. In 1999, he was chosen by the Association for Symbolic Logic to deliver the Gödel Lecture.

In 2013, the Government of Ontario honored Cook with the Order of Ontario, which is the highest award given in Ontario. In 2012, he received the Gerhard Herzberg Canada Gold Medal for Science and Engineering, the highest honor for scientists and engineers in Canada. This award is given by NSERC to recognize long-term excellence and the wide influence of research in natural sciences or engineering. In 2015, Cook was named an Officer of the Order of Canada.

In 2015, Cook was awarded the BBVA Foundation Frontiers of Knowledge Award in the Information and Communication Technologies category. The award recognized his role in explaining what computers can and cannot solve efficiently. His work has had a major impact in areas where complex calculations are important.

Cook has supervised many MSc students, and 36 PhD students have completed their degrees under his guidance.

Personal life

Cook lives with his wife in Toronto. They have two sons. One of their sons is Gordon Cook, an Olympic sailor.