En la teoría de la complejidad computacional , el teorema de Cook-Levin , también conocido como teorema de Cook , establece que el problema de satisfacibilidad booleano es NP-completo . Es decir, está en NP , y cualquier problema en NP puede reducirse en tiempo polinomial mediante una máquina de Turing determinista al problema de satisfacibilidad booleano.
El teorema lleva el nombre de Stephen Cook y Leonid Levin .
Una consecuencia importante de este teorema es que si existe un algoritmo de tiempo polinomial determinista para resolver la satisfacibilidad booleana, entonces cada problema de NP puede resolverse mediante un algoritmo de tiempo polinomial determinista. La cuestión de si existe tal algoritmo para la satisfacibilidad booleana es, por tanto, equivalente al problema P versus NP , que se considera ampliamente el problema no resuelto más importante en la informática teórica.
Contribuciones
El concepto de completitud de NP fue desarrollado en paralelo a finales de la década de 1960 y principios de la de 1970 por investigadores de América del Norte y la URSS . En 1971, Stephen Cook publicó su artículo "La complejidad de los procedimientos de demostración de teoremas" [1] en las actas de la conferencia del Simposio ACM sobre Teoría de la Computación, recientemente fundado . El artículo posterior de Richard Karp , "Reducibilidad entre problemas combinatorios", [2] generó un interés renovado en el artículo de Cook al proporcionar una lista de 21 problemas NP completos . Cook y Karp recibieron un premio Turing por este trabajo.
El interés teórico en la completitud de NP también se vio reforzado por el trabajo de Theodore P. Baker, John Gill y Robert Solovay, quienes demostraron que la resolución de problemas de NP en modelos de máquinas de Oracle requiere un tiempo exponencial. Es decir, existe un oráculo A tal que, para todas las clases de tiempo complejidad deterministas subexponenciales T, la clase de complejidad NP relativizada A no es un subconjunto de T A . En particular, para este oráculo, P A ≠ NP A . [3]
En la URSS, M. Dekhtiar publicó en 1969 un resultado equivalente al de Baker, Gill y Solovay. [4] Posteriormente, el artículo de Leonid Levin , "Problemas de búsqueda universal", [5] se publicó en 1973, aunque se mencionó en las charlas y se envió para su publicación unos años antes.
El enfoque de Levin fue ligeramente diferente al de Cook y Karp en que consideró los problemas de búsqueda , que requieren encontrar soluciones en lugar de simplemente determinar la existencia. Proporcionó 6 de estos problemas de búsqueda NP-completos, o problemas universales . Además, encontró para cada uno de estos problemas un algoritmo que lo resuelve en el tiempo óptimo (en particular, estos algoritmos se ejecutan en tiempo polinómico si y solo si P = NP ).
Definiciones
Un problema de decisión está en NP si puede resolverse mediante un algoritmo no determinista en tiempo polinomial .
Una instancia del problema de satisfacibilidad booleana es una expresión booleana que combina variables booleanas utilizando operadores booleanos .
Una expresión es satisfactoria si hay alguna asignación de valores de verdad a las variables que hace que toda la expresión sea verdadera.
Ocurrencia
Dado cualquier problema de decisión en NP, construya una máquina no determinista que lo resuelva en tiempo polinomial. Luego, para cada entrada a esa máquina, construya una expresión booleana que calcule si esa entrada específica se pasa a la máquina, la máquina funciona correctamente y la máquina se detiene y responde "sí". Entonces, la expresión puede satisfacerse si y solo si hay una manera de que la máquina funcione correctamente y responda "sí", por lo que la satisfacción de la expresión construida es equivalente a preguntar si la máquina responderá "sí" o no.
Prueba
Esta prueba se basa en la dada por Garey y Johnson. [6]
Hay dos partes para demostrar que el problema de satisfacibilidad booleano (SAT) es NP-completo. Uno es mostrar que el SAT es un problema de NP. La otra es mostrar que cada problema de NP puede reducirse a una instancia de un problema SAT mediante una reducción de varios uno en tiempo polinomial .
SAT está en NP porque cualquier asignación de valores booleanos a variables booleanas que se afirma que satisface la expresión dada puede verificarse en tiempo polinómico mediante una máquina de Turing determinista. (Los enunciados verificables en tiempo polinomial por una máquina de Turing determinista y que pueden resolverse en tiempo polinómico por una máquina de Turing no determinista son totalmente equivalentes, y la demostración se puede encontrar en muchos libros de texto, por ejemplo, Introducción a la teoría de la computación de Sipser , sección 7.3. ., así como en el artículo de Wikipedia sobre NP ).
Ahora suponga que un problema dado en NP puede ser resuelto por la máquina de Turing no determinista M = ( Q , Σ, s , F , δ) , donde Q es el conjunto de estados, Σ es el alfabeto de símbolos de cinta, s ∈ Q es el estado inicial, F ⊆ Q es el conjunto de estados de aceptación, y δ ⊆ (( Q \ F ) × Σ) × ( Q × Σ × {−1, +1}) es la relación de transición. Suponga además que M acepta o rechaza una instancia del problema en el tiempo p ( n ) donde n es el tamaño de la instancia yp es una función polinomial.
Para cada entrada, I , especificamos una expresión booleana que es satisfiable si y sólo si la máquina M acepta Me .
La expresión booleana utiliza las variables establecidas en la siguiente tabla. Aquí, q ∈ Q , - p ( n ) ≤ i ≤ p ( n ), j ∈ Σ y 0 ≤ k ≤ p ( n ) .
Variables | Interpretación prevista | ¿Cuantos? |
---|---|---|
T i, j, k | Verdadero si la celda de cinta i contiene el símbolo j en el paso k del cálculo. | O ( p ( n ) 2 ) |
Hola , k | Verdadero si el cabezal de lectura / escritura de M está en la celda de cinta i en el paso k del cálculo. | O ( p ( n ) 2 ) |
Q q, k | Verdadero si M está en el estado q en el paso k del cálculo. | O ( p ( n )) |
Defina la expresión booleana B como la conjunción de las subexpresiones en la siguiente tabla, para todo - p ( n ) ≤ i ≤ p ( n ) y 0 ≤ k ≤ p ( n ) :
Expresión | Condiciones | Interpretación | ¿Cuantos? |
---|---|---|---|
La celda de cinta i contiene inicialmente el símbolo j | Contenido inicial de la cinta. Para i > n -1 e i <0, fuera de la entrada real, el símbolo inicial es el símbolo especial predeterminado / en blanco. | O ( p ( n )) | |
Estado inicial de M . | 1 | ||
Posición inicial del cabezal de lectura / escritura. | 1 | ||
j ≠ j ′ | Como máximo, un símbolo por celda de cinta. | O ( p ( n ) 2 ) | |
Al menos un símbolo por celda de cinta. | O ( p ( n ) 2 ) | ||
j ≠ j ′ | La cinta permanece sin cambios a menos que esté escrita. | O ( p ( n ) 2 ) | |
¬ Q q, k ∨ ¬ Q q ′, k | q ≠ q ′ | Solo un estado a la vez. | O ( p ( n )) |
¬ H yo, k ∨ ¬ H yo ′, k | yo ≠ yo ′ | Solo una posición de cabeza a la vez. | O ( p ( n ) 3 ) |
k < p ( n ) | Posibles transiciones en el paso de cálculo k cuando la cabeza está en la posición i . | O ( p ( n ) 2 ) | |
Debe terminar en un estado de aceptación, a más tardar en el paso p ( n ). | 1 |
Si hay un cálculo aceptable para M en la entrada I , entonces B se puede satisfacer asignando a T i, j, k , H i, k y Q i, k sus interpretaciones previstas. Por otro lado, si B es satisfactorio, entonces hay un cálculo de aceptación para M en la entrada I que sigue los pasos indicados por las asignaciones a las variables.
Hay O ( p ( n ) 2 ) variables booleanas, cada una codificable en el espacio O (log p ( n )) . El número de cláusulas es O ( p ( n ) 3 ) por lo que el tamaño de B es O (log ( p ( n )) p ( n ) 3 ). Por lo tanto, la transformación es ciertamente una reducción de muchos uno en tiempo polinómico, según se requiera.
Consecuencias
La prueba muestra que cualquier problema en NP puede reducirse en tiempo polinomial (de hecho, el espacio logarítmico es suficiente) a una instancia del problema de satisfacibilidad booleano. Esto significa que si el problema de satisfacibilidad booleano pudiera resolverse en tiempo polinomial mediante una máquina de Turing determinista , entonces todos los problemas en NP podrían resolverse en tiempo polinomial, por lo que la clase de complejidad NP sería igual a la clase de complejidad P.
La importancia de NP-completitud quedó clara en la publicación en 1972 del artículo histórico de Richard Karp , "Reducibilidad entre problemas combinatorios", en el que mostró que 21 problemas combinatorios y teóricos de gráficos diversos , cada uno de los cuales es infame por su intratabilidad, son NP -completo. [2]
Karp mostró que cada uno de sus problemas era NP-completo al reducir otro problema (que ya se ha demostrado que es NP-completo) a ese problema. Por ejemplo, mostró que el problema 3SAT (el problema de satisfacibilidad booleana para expresiones en forma normal conjuntiva con exactamente tres variables o negaciones de variables por cláusula) era NP-completo al mostrar cómo reducir (en tiempo polinómico) cualquier instancia de SAT a una instancia equivalente de 3SAT. (Primero modificas la demostración del teorema de Cook-Levin, de modo que la fórmula resultante esté en forma normal conjuntiva, luego introduces nuevas variables para dividir cláusulas con más de 3 átomos. Por ejemplo, la cláusula (A ∨ B ∨ C ∨ D) se puede reemplazar por la conjunción de cláusulas (A ∨ B ∨ Z) ∧ (¬Z ∨ C ∨ D), donde Z es una nueva variable que no se utilizará en ningún otro lugar de la expresión. Cláusulas con menos de 3 átomos se puede rellenar; por ejemplo, A se puede reemplazar por (A ∨ A ∨ A), y (A ∨ B) se puede reemplazar por (A ∨ B ∨ B)).
Garey y Johnson presentaron más de 300 problemas NP-completos en su libro Computers and Intractability: A Guide to the Theory of NP-Completeness , [6] y todavía se están descubriendo nuevos problemas dentro de esa clase de complejidad.
Aunque muchas instancias prácticas de SAT pueden resolverse mediante métodos heurísticos , la cuestión de si existe un algoritmo determinista de tiempo polinomial para SAT (y, en consecuencia, todos los demás problemas NP-completos) sigue siendo un problema famoso sin resolver, a pesar de décadas de intenso esfuerzo por parte de teóricos de la complejidad, lógicos matemáticos y otros. Para obtener más detalles, consulte el artículo Problema P versus NP .
Referencias
- ^ Cook, Stephen (1971). "La complejidad de los procedimientos de demostración de teoremas" . Actas del Tercer Simposio Anual ACM sobre Teoría de la Computación . págs. 151-158. doi : 10.1145 / 800157.805047 .
- ^ a b Karp, Richard M. (1972). "Reducibilidad entre problemas combinatorios" (PDF) . En Raymond E. Miller; James W. Thatcher (eds.). Complejidad de los cálculos informáticos . Nueva York: Pleno. págs. 85-103. ISBN 0-306-30707-3.
- ^ TP Baker; J. Gill; R. Solovay (1975). "Relativizaciones de la pregunta P = NP". Revista SIAM de Computación . 4 (4): 431–442. doi : 10.1137 / 0204037 .
- ^ Dekhtiar, M. (1969). "Sobre la imposibilidad de eliminar la búsqueda exhaustiva en el cálculo de una función relativa a su gráfico". Actas de la Academia de Ciencias de la URSS (en ruso). 14 : 1146-1148.
- ^ Levin, Leonid (1973). "Универсальные задачи перебора" [Problemas de búsqueda universal]. Problemas de transmisión de información (en ruso). 9 (3): 115-116. Traducido al inglés por Trakhtenbrot, BA (1984). "Una encuesta de enfoques rusos a los algoritmos de perebor (búsquedas de fuerza bruta)". Anales de la historia de la informática . 6 (4): 384–400. doi : 10.1109 / MAHC.1984.10036 .
- ^ a b Garey, Michael R .; David S. Johnson (1979). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . WH Freeman. ISBN 0-7167-1045-5.