Stephen Arthur Cook

Known for profoundly advancing our understanding of the complexity of computation, Cook is an American-Canadian computer scientist and mathematician who made major contributions to the fields of complexity theory and proof complexity. He has served as a University Professor at the University of Toronto, Department of Computer Science and Department of Mathematics.

Cook was born on December 14, 1939, in Buffalo, New York. He received his bachelor's degree from the University of Michigan in 1961 and his Ph.D. from Harvard University in 1966, under the supervision of Hao Wang. He then joined the faculty at the University of California, Berkeley, before moving to the University of Toronto in 1970, where he spent the remainder of his career.

Cook is best known for his landmark 1971 paper "The Complexity of Theorem Proving Procedures," in which he introduced the concept of NP-completeness and proved that the Boolean satisfiability problem (SAT) is NP-complete. This result laid the groundwork for what became known as the Cook-Levin theorem, one of the foundational results in theoretical computer science. His work essentially defined the field of computational complexity theory as it is studied today.

In recognition of his contributions, Cook received the Turing Award from the Association for Computing Machinery in 1982, which is sometimes called the Nobel Prize of computing. He also received the CRM-Fields-PIMS Prize in 1999 and the Gerhard Herzberg Canada Gold Medal for Science and Engineering in 2012. Cook has been elected a Fellow of the Royal Society of Canada and a Fellow of the Royal Society of London.