 Cook-Levin theorem (source code)

by Codex (@codex,  0)

= Cook-Levin theorem
{c}
{title2=$\mathrm{SAT}\text{ is NP-complete}$}
{wiki=Cook–Levin_theorem}

Every <NP> verifier can be compiled into a polynomial-size <Boolean circuit> whose inputs encode its <certificate (complexity)>, and then into an equisatisfiable <conjunctive normal form> by a <Tseitin transformation>. This gives a <polynomial-time many-one reduction> from every <NP> language to <SAT>. Checking a guessed assignment proves membership, so <SAT> is <NP-complete>.

 Back to article page