= Stephen Cook
{c}
{wiki}
= Stephen A. Cook
{c}
{synonym}
<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>.<The Complexity of Theorem-Proving Procedures by Stephen A. Cook>[Section 1, Theorem 1 and construction in its proof]{ref}
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>.https://www.cs.toronto.edu/~sacook/[Research publications and Logical Foundations of Proof Complexity]{ref}
\Image[https://commons.wikimedia.org/wiki/Special:Redirect/file/2012-06-15%20Stephen%20A.%20Cook.jpg?width=250]
{title=Portrait of <Stephen Cook>}
{description=orcmid, Flickr photograph, 15 June 2012. https://creativecommons.org/licenses/by/2.0/[Creative Commons Attribution 2.0 Generic.], via Wikimedia Commons.}
{source=https://commons.wikimedia.org/wiki/File:2012-06-15_Stephen_A._Cook.jpg}
{width=250}
Back to article page
