Skip to content
Fellows Directory

Stephen Cook

Stephen Cook

Professor Stephen Cook FRS

Fellow


Elected: 1998

Biography

Stephen Cook has made pioneering contributions to the theory of computational complexity. His discovery of the NP-completeness phenomenon, besides reshaping that field, has influenced almost all areas of computer science, and provides a technique for computer users in diverse domains to determine whether their problems as formulated are computationally tractable. He has provided numerous further insights into the limits of computation by proving lower bounds on the time and space resources needed for performing specific sequential and parallel computations.

His work in mathematical logic has given a new understanding of the minimal lengths of proofs. It has also provided novel efficient algorithms for such fundamental problems as pattern matching of strings and integer division by circuits. He has repeatedly demonstrated the unreasonable power of mathematics for describing computational phenomena.

Interest and expertise

Subject groups

  • Mathematics
    • Computer science (excl engineering aspects)

Keywords

computational complexity

Was this page useful?
Thank you for your feedback
Thank you for your feedback. Please help us improve this page by taking our short survey.