Cook demostró este teorema en su artículo de 1971 "The Complexity of Theorem Proving Procedures".
La expresión booleana utiliza las variables descritas en la siguiente tabla en la cual q ∈ Q, −p(n) ≤ i ≤ p(n), j ∈ Σ, y 0 ≤ k ≤ p(n): Se definen las expresiones booleanas “B” como la conjunción de las cláusulas de la siguiente tabla, para todo −p(n) ≤ i ≤ p(n) y 0 ≤ k ≤ p(n): Si la máquina acepta la entrada “I”, es decir, si existe una sucesión de estados válidos para M con entrada I, entonces B es satisfacible, al asociar a las cláusulas Tijk, Hik y Qik sus correspondientes interpretaciones.
El número de cláusulas es O(p(n)²).
Esto significa que si SAT pudiera ser resuelto en tiempo polinómico en una máquina de Turing determinista, entonces todos los problemas pertenecientes a NP podrían ser resueltos en tiempo polinómico, por lo que la clase NP sería idéntica a la clase P. El teorema de Cook fue la primera prueba de existencia de problemas NP-Completos.
Garey y Johnson presentan más de 300 problemas en NP-Completo en su libro Computers and Intractability: A Guide to the Theory of NP-Completeness, y muchos otros nuevos problemas son agregados frecuentemente a esta clase de complejidad.