Stephen A. Cook 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 open theoretical computer science's greatest unsolved question - whether complexity classes P and NP are equivalent, the answer to which has eluded researchers since.

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. He 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 Computer Science Department and Mathematics Department.

External link

• Home page of Stephen A. Cook
• Stephen A. Cook's students