|
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.
As of 2004, Cook is currently a professor in the Mathematics
Department at the University of Toronto.
|