Teorema de Cook
En teoría de la complejidad computacional, el Teorema de Cook establece lo siguiente:
|
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 Tijk, Hik y Qik 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 NP 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 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 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 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.
Referencias
- Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.
- ↑ Levin, Leonid (1973). «Universal'nye perebornye zadachi». Problemy Peredachi Informatsii 9 (3): 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): 384-400. Archivado desde el original el 19 de noviembre de 2015.