# Stephen Cook

Stephen Arthur Cook OOnt ( born December 14, 1939 in Buffalo, New York) is a professor of computer science at the University of Toronto in Canada. Its main activity is the complexity theory; Cook works alongside his teaching but also at the interface of logic and computability theory.

Cook was in theoretical computer science known by the set of Cook: "SAT is NP-complete ". In 1982 he received the Turing Award for this discovery.

In 1990 he gave a plenary lecture at the ICM in Kyoto (Computational complexity of higher type functions).

## Life

Cook grew up as the son of a chemistry professor and an English teacher near Buffalo, New York, on. From 1957, he studied engineering at the University of Michigan, moved to two and a half years to mathematics and reached the 1961 undergraduate degrees. He studied at Harvard University, where a course of his later thesis supervisor Wang Hao sparked his interest in computers. In 1962 he was master of mathematics, in 1966 with the thesis On the Minimum Computation Time of Functions ( therein including the Toom - Cook algorithm) Ph.D. After studying the end, he became an assistant professor at the Mathematics Department of the University of California, Berkeley. After him there was denied a job for life, he joined in 1970 as an associate professor at the newly founded Faculty of computer science at the University of Toronto, where he initially continued in mathematics lectures.

In 1971, he formalized in the paper The Complexity of Theorem Proving Procedures, the Polynomialzeitreduktion (also: Cook reduction ), and reasoned with the set of Cook the problem of NP- completeness, and in particular the P- NP problem. The following year, this work of Cook's brief Berkeley colleague Richard M. Karp was popularized and expanded by Karp's 21 NP- complete problems.

In 1975 he became a full professor, and in 1985 he received the honorary title of University Professor.

Cook is Steacie Fellow, Killiam Research Fellow, ACM Fellow, a Fellow of the Royal Society of London and the Royal Society of Canada, and was elected to the National Academy of Sciences and the American Academy of Arts and Sciences. In 1982 he received the Turing Award in 1999, he received the CRM -Fields Prize and was Godel Lecturer. He was awarded the 2012 Gerhard Herzberg Canada Gold Medal for Science and Engineering.

Cook's first graduate student, Walter Savitch ( set of Savitch ), followed almost 30 more.