Encyclopedia > Stephen Cook

  Article Content

Stephen Cook

Stephen A. Cook, 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 a proof that the boolean satisfiability problem was 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.

Stephen Cook is currently a professor at the University of Toronto.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Springs, New York

... the age of 18, 6.3% from 18 to 24, 31.0% from 25 to 44, 26.9% from 45 to 64, and 13.5% who are 65 years of age or older. The median age is 40 years. For every 100 ...

 
 
 
This page was created in 30.9 ms