Stephen Cook
fl. 1939, Buffalo, New York, United States
American-Canadian computer scientist and mathematician who founded the theory of NP-completeness, formulating the P versus NP question and proving the Cook–Levin theorem.
Stephen Cook was born in Buffalo, New York, and earned his PhD in mathematics from Harvard University in 1966. After an assistant professorship at the University of California, Berkeley, he joined the University of Toronto in 1970, where he spent the rest of his career and became a Canadian citizen.
Cook's 1971 paper "The Complexity of Theorem-Proving Procedures" introduced the notion of NP-completeness and proved that the Boolean satisfiability problem (SAT) is NP-complete — the Cook–Levin theorem, independently discovered by Leonid Levin in the Soviet Union. The paper formulated what became the P versus NP problem: whether every problem whose solutions can be verified quickly can also be solved quickly. It launched computational complexity theory as a field and remains one of the seven Clay Millennium Prize Problems, still open today.
For this work Cook received the 1982 ACM Turing Award, computer science's highest honour. He continued to work on complexity theory and proof complexity at the University of Toronto, where he is now University Professor Emeritus.
Workplaces: University of California, Berkeley, University of Toronto
Canada, United States