Teorema de Cook

En teoría de la complejidad computacional, el Teorema de Cook establece lo siguiente:

El Problema de satisfacibilidad booleana (SAT) es NP-completo.

Cook demostró este teorema en su artículo de 1971 "The Complexity of Theorem Proving Procedures".

El teorema fue demostrado independientemente por Leonid Levin aproximadamente en la misma fecha, por lo que algunas veces es llamado Teorema de Cook-Levin.^[1]​

Un problema de decisión pertenece a NP si puede ser resuelto por una Máquina de Turing indeterminista en tiempo polinómico.

Se dice que un problema de decisión es NP-completo si pertenece a NP y si todo problema perteneciente a NP puede ser reducido a él utilizando una transformación polinómica.

Una instancia del problema SAT es una expresión booleana que combina variables booleanas con operadores booleanos. Una expresión es satisfacible si existe una asignación de valores booleanos para las variables de esa expresión que hace que la expresión completa sea verdadera.

El problema de SAT pertenece a NP dado que puede ser resuelto con una máquina de Turing no determinista que genere todas las posibles combinaciones de valores para las variables de la expresión y, en forma no determinista, intente verificar si alguna de ellas hace que la expresión se evalúe en verdadero, en cuyo caso acepta la entrada.

Supóngase que un problema perteneciente a NP es resuelto por una máquina de Turing M = (Q, Σ, i, F, δ) (donde Q es el conjunto de estados, Σ es el alfabeto de símbolos de la cinta, i ∈ Q es el estado inicial, F ⊆ Q es el conjunto de estados de aceptación y δ ⊆ Q × Σ × Q × Σ × {−1,+1} el conjunto de transiciones) y que M acepta o rechaza una instancia del problema en tiempo p(n) donde n es el tamaño de la instancia y p es una función polinómica.

Para cada instancia “I” del problema se describe una expresión booleana que es satisfacible si y sólo si la máquina M acepta a I.

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 T_ijk, H_ik y Q_ik sus correspondientes interpretaciones. Por otra parte, si B es satisfacible, entonces existe un cálculo de la máquina M que partiendo de la entrada “I” conduce a un estado de aceptación que sigue los pasos indicados por la asignación de variables.

¿Qué tamaño tiene B? “B” utiliza O(p(n)²) variables booleanas, cada una de las cuales se codifica en espacio O(log p(n)). El número de cláusulas es O(p(n)²). de manera que el tamaño de B es O((log p(n)) p(n)²), lo cual es polinómico con respecto al tamaño n de la entrada, de manera que la transformación es ciertamente polinómica como se requiere.

Se puede mostrar que cualquier problema perteneciente a NP puede ser reducido en tiempo polinómico a una instancia del problema SAT. 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. Otras pruebas de pertenencia a NP-Completo generalmente reducen el problema que se desea demostrar a un problema que ya se sabe que pertenece a NP-completo. Por ejemplo, se puede demostrar que el problema 3-SAT (problema de satisfacibilidad de expresiones booleanas en forma normal conjuntiva con tres variables o negaciones de variables por cláusula) es NP-Completo mostrando cómo reducir cualquier instancia de SAT en una instancia equivalente de 3-SAT.

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.

---