Stephen Cook

Infobox_Scientist
name = Stephen Arthur Cook

---

image_width = 150px
caption =
birth_date = birth date and age|1939|12|14
birth_place = Buffalo, New York
death_date =
death_place =
residence =
citizenship =
nationality =
ethnicity =
field = Computer Science
work_institution = University of California, Berkeley
University of Toronto
alma_mater = Harvard University
doctoral_advisor = Hao Wang
doctoral_students = Walter Savitch
known_for = NP-completeness
author_abbreviation_bot =
author_abbreviation_zoo =
prizes = Turing Award
religion =
footnotes =

Stephen Arthur Cook (born December 14, 1939, Buffalo, New York) is a noted computer scientist.

Cook formalised the notion of NP-completeness in a famous 1971 paper "The Complexity of Theorem Proving Procedures", which also contained Cook's theorem, a proof that the boolean satisfiability problem is NP-complete. The paper left unsolved the greatest open question in theoretical computer science - whether complexity classes P and NP are equivalent.

Cook received the Turing Award in 1982 for his discovery. His citation reads:

"For his advancement of our understanding of the complexity of computation in a significant and profound way. His seminal paper, "The Complexity of Theorem Proving Procedures," presented at the 1971 ACM SIGACT Symposium on the Theory of Computing, laid the foundations for the theory of NP-Completeness. The ensuing exploration of the boundaries and nature of NP-complete class of problems has been one of the most active and important research activities in computer science for the last decade."

He received his Bachelor's degree in 1961 from the University of Michigan. At Harvard University, he received his Master's degree in 1962 and his Ph.D. in 1966. From 1966 to 1970 he was Assistant Professor at the University of California, Berkeley in the math department, which infamously denied him tenure. In a speech celebrating the 30th anniversary of the Berkeley EECS department, fellow Turing Award winner and Berkeley professor Richard Karp said that, "It is to our everlasting shame that we were unable to persuade the math department to give him tenure." [ [http://www.eecs.berkeley.edu/BEARS/CS_Anniversary/karp-talk.html A Personal View of Computer Science at Berkeley - Richard Karp ] ] Cook then joined the faculty at the University of Toronto in 1970 as an Associate Professor, and was promoted to Professor in 1975 and University Professor in 1985 in the [http://www.cs.utoronto.ca Computer Science Department] and [http://www.math.utoronto.ca/dept/dirfac.html Mathematics Department] .

References

External links

* [http://www.cs.toronto.edu/~sacook/ Home page of Stephen A. Cook]
* [http://www.cbi.umn.edu/oh/display.phtml?id=341 Oral history interview with Stephen Cook] at Charles Babbage Institute, University of Minnesota. Cook discusses his education at the University of Michigan and Harvard University and early work at the University of California, Berkeley, and his growing interest in problems of computational complexity. Cook recounts his move to the University of Toronto in 1970 and the reception of his work on NP-completeness, leading up to his A.M. Turing Award.
* [http://www.nserc.gc.ca/news/2006/p060214_cook.htm NSERC biography of Stephen Cook]
*

Gallery

Persondata
NAME= Cook, Stephen Arthur
ALTERNATIVE NAMES=
SHORT DESCRIPTION= Computer scientist
DATE OF BIRTH= 1939
PLACE OF BIRTH= Buffalo, New York
DATE OF DEATH=
PLACE OF DEATH=