Stephen Cook is a computer scientist whose 1971 paper established a foundational connection between the class NP and Boolean satisfiability. The Cook-Levin theorem is expressed in modern terminology by saying that Boolean satisfiability is NP-complete.[ref]
The Complexity of Theorem-Proving Procedures by Stephen A. Cook. Section 1, Theorem 1 and construction in its proof
The proof encodes the possible steps of a polynomially bounded Nondeterministic Turing machine as a Boolean formula. A satisfying assignment describes an accepting computation, and the formula has polynomial size. This makes polynomial-time reduction a way to compare apparently different computational tasks: an efficient general solver for the encoded problem would solve every problem in NP. Cook's broader work also connects mathematical logic with proof complexity.[ref]
https://www.cs.toronto.edu/~sacook/. Research publications and Logical Foundations of Proof Complexity
Portrait of Stephen Cook
. orcmid, Flickr photograph, 15 June 2012. Creative Commons Attribution 2.0 Generic., via Wikimedia Commons. Source.
Stephen Cook is a prominent computer scientist known for his foundational work in computational complexity theory. He is best known for formulating the concept of NP-completeness in 1971, which provides a framework for understanding the inherent difficulty of computational problems. Cook's theorem demonstrates that the Boolean satisfiability problem (SAT) is NP-complete, meaning that if there is a polynomial-time algorithm for SAT, then there is a polynomial-time algorithm for all problems in the class NP.
New to topics? Read the docs here!