Teorema de Cook

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.