Stephen A. Cook
Stephen Arthur Cook OOnt (born December 14, 1939 in Buffalo , New York ) is Professor of Computer Science at the University of Toronto in Canada . His main field of activity is complexity theory ; In addition to his teaching activities, Cook also works at the interface between logic and predictability theory .
Cook became famous in theoretical computer science through Cook's sentence : " 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 near Buffalo , New York , the son of a chemistry professor and English teacher . From 1957 he studied engineering at the University of Michigan , switched to mathematics after two and a half years and achieved his bachelor's degree in 1961. He studied further at Harvard University , where a course given by his later PhD supervisor Hao Wang aroused his interest in computers. In 1962 he became a Master of Mathematics, in 1966 with the thesis On the Minimum Computation Time of Functions (including the Toom Cook algorithm ), Ph.D. After graduating, he became an assistant professor in the math faculty at the University of California, Berkeley . After he was denied a lifelong position there , he moved to the newly founded Faculty of Computer Science at the University of Toronto as an associate professor, where he initially also gave mathematics lectures.
In 1971, in the paper The Complexity of Theorem Proving Procedures, he formalized the polynomial time reduction (also: Cook reduction ), and founded the problem of NP completeness and in particular the P-NP problem with Cook 's theorem . The following year, Cook's short-term Berkeley colleague Richard M. Karp popularized this work and expanded it to include Karp's 21 NP-complete problems .
In 1975 he became a full professor, and in 1985 he was awarded the honorary title of University Professor .
Cook is a Steacie Fellow, Killiam Research Fellow, ACM Fellow, 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 . He is a corresponding member of the Academy of Sciences in Göttingen . In 1982 he received the Turing Award, in 1999 he received the CRM Fields Prize and was a Gödel Lecturer . He was awarded the Gerhard Herzberg Canada Gold Medal for Science and Engineering for 2012 and the BBVA Foundation Frontiers of Knowledge Award for 2015.
Cook's first PhD student was Walter Savitch ( Savitch Theorem ), and nearly 30 more followed.
Web links
- Cook's site at the University of Toronto (English)
- Oral History Interview of the Charles Babbage Institute, University of Minnesota with Stephen A. Cook 2002 (English)
| personal data | |
|---|---|
| SURNAME | Cook, Stephen A. |
| ALTERNATIVE NAMES | Cook, Stephen Arthur (full name) |
| BRIEF DESCRIPTION | American computer scientist, Cook's Theorem |
| DATE OF BIRTH | December 14, 1939 |
| PLACE OF BIRTH | Buffalo , New York |