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.