
related topics 
{work, book, publish} 
{math, number, function} 
{theory, work, human} 
{son, year, death} 

Stephen Arthur Cook (born December 14, 1939, Buffalo, New York) is a renowned AmericanCanadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity. He is currently a University Professor at the University of Toronto, Department of Computer Science and Department of Mathematics.
Contents
Biography
Cook received his Bachelor's degree in 1961 from the University of Michigan, and his Master's degree and Ph.D. from Harvard University, respectively in 1962 and 1966. He joined the University of California, Berkeley, mathematics department in 1966 as an Assistant Professor, and stayed there till 1970 when he was denied reappointment. 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."^{[1]} Cook joined the faculty of University of Toronto, Computer Science and Mathematics Departments in 1970 as an Associate Professor, where he was promoted to Professor in 1975 and University Professor in 1985.
Research
Cook is considered one of the forefathers of computational complexity theory.
During his PhD, Cook worked on complexity of functions, mainly on multiplication. He received his PhD in 1966. A few years later, in his seminal 1971 paper "The Complexity of Theorem Proving Procedures",^{[2]}^{[3]} Cook formalized the notions of polynomialtime reduction (a.k.a. Cook reduction) and NPcompleteness, and proved the existence of an NPcomplete problem by showing that the Boolean satisfiability problem (usually known as SAT) is NPcomplete. This theorem was proven independently by Leonid Levin in the Soviet Union, and has thus been given the name the CookLevin theorem. The paper also formulated the most famous problem in computer science, the P vs. NP problem. Informally, the "P vs. NP" question asks whether every optimization problem whose answers can be efficiently verified for correctness/optimality can be solved optimally with an efficient algorithm. Given the abundance of such optimization problems in everyday life, a positive answer to the "P vs. NP" question would likely have profound practical and philosophical consequences.
Full article ▸


related documents 
Robert Freitas 
Ross J. Anderson (professor) 
Jeffrey Simpson 
Wikipedia:Nupedia and Wikipedia 
Archibald Hill 
James Tiptree, Jr. Award 
Barry Lopez 
Smithsonian (magazine) 
Jane Urquhart 
Bartel Leendert van der Waerden 
E. B. White 
Autosport 
Ahmed Zewail 
Christopher J. Date 
Richard Hamming 
MatthÃ¤us Merian 
Niklaus Wirth 
Xavier Serbia 
Sultan Bashiruddin Mahmood 
Heinrich Kiepert 
The World Factbook 
Academy Award for Animated Short Film 
Roald Hoffmann 
Aurel Stein 
Sam Lundwall 
Nuffield College, Oxford 
Open publishing 
On Writing 
Aldine Press 
Robert Noyce 
