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. Stephen Cook (1971)

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]

Definiciones

Un problema de decisión pertenece a NP si puede ser resuelto en 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.

Demostración

El problema de SAT pertenece a NP dado que puede ser resuelto con una máquina de Turing no-determinista que genera todas las posibles combinaciones de valores para las variables de la expresión y, en forma no-determinista intenta 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):

Variables	Interpretación	¿Cuántas?
Tijk	Verdadero si la casilla i de la cinta contiene el símbolo j en el paso k del cálculo.	O(p(n)²)
Hik	Verdadero si el cabezal de la máquina está posicionado en la casilla i en el paso k del cálculo.	O(p(n)²)
Qqk	Verdadero si M está en el estado q en el paso k del cálculo.	O(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):

Cláusulas	Condiciones	Interpretación	¿Cuántas?
Tij0	La casilla i de la entrada contiene el símbolo j en la configuración inicial.	Contenido inicial de la cinta.	O(p(n))
Qs0		Estado inicial de M	O(1)
H00		Posición inicial del cabezal de la máquina.	O(1)
Tijk → ¬ Tij′k	j ≠ j′	Un símbolo por cada celda de la cinta.	O(p(n)²)
Tijk = Tij(k+1) ∨ Hik		La cinta no cambia a menos que la transición escriba en la cinta.	O(p(n)²)
Qqk → ¬ Qq′k	q ≠ q′	Sólo un estado en cada momento.	O(p(n))
Hik → ¬ Hi′k	i ≠ i′	Sólo una posición del cabezal en cada momento.	O(p(n))
La disyunción de las cláusulas (Hik ∧ Qqk ∧ Tiσk) → (H(i+d)(k+1) ∧ Qq′(k+1) ∧ Tiσ′(k+1))	(q, σ, q′, σ′, d) ∈ δ	Posible transición en el paso k del cálculo cuando el cabezal está en la posición i.	O(p(n)²)
La disyunción de las cláusulas Qf(p(n))	f ∈ F.	Debe terminar en un estado de aceptación.	O(1)

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.

Consecuencias

Se puede mostrar que cualquier problema perteneciente a NPI puede ser reducido en tiempo polinómico en 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 NPI podrían ser resueltos en tiempo polinómico, por lo que la clase NPI sería idéntica a la clase P.

El teorema de Cook fue la primera prueba de existencia de problemas NPI-completos. Otras pruebas de pertenencia a NPI-completo generalmente reducen el problema que se desea demostrar en 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 NPI-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 NPI-completo en su libro Computers and Intractability: A Guide to the Theory of NPI-Completeness, y muchos otros nuevos problemas son agregados frecuentemente a esta clase de complejidad.

Referencias

• Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.

1. ↑ Levin, Leonid (1973). «Universal'nye perebornye zadachi». Problemy Peredachi Informatsii 9 (3):  pp. 265–266.  Traducido al Inglés en "Universal Search Problems", en Trakhtenbrot, B. A. (1984). «A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms». Annals of the History of Computing 6 (4):  pp. 384-400. http://csdl.computer.org/comp/mags/an/1984/04/a4384abs.htm.