Teorema de Cook-Levin - Cook–Levin theorem

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 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 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" 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", 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, en 1975, 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 .

En la URSS, M. Dekhtiar publicó en 1969 un resultado equivalente al de Baker, Gill y Solovay. Posteriormente, el artículo de Leonid Levin , "Problemas de búsqueda universal", 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.

Idea

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

Esquematizada aceptar cálculo por la máquina M .

Esta prueba se basa en la dada por Garey y Johnson.

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 supuestamente satisfacen la expresión dada puede verificarse en tiempo polinomial mediante una máquina de Turing determinista. (Los enunciados verificables en tiempo polinómico por una máquina de Turing determinista y que pueden resolverse en tiempo polinomial 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 \in Q$ es el estado inicial, $F \subseteq 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 \in Q, - p (n) \leq i \leq p (n), j \in Σ$ y $0 \leq k \leq 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 ) ² )
Hola _{, k}	Es cierto que si el M ' cabeza de lectura / escritura de s está en celda de la cinta i en el paso k del cálculo.	O ( p ( n ) ² )
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) \leq i \leq p (n)$ y $0 \leq k \leq p (n)$ :

Expresión	Condiciones	Interpretación	¿Cuantos?
${\ Displaystyle T_ {i, j, 0}}$	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. ${\ Displaystyle I}$	O ( p ( n ))
${\ Displaystyle Q_ {s, 0}}$		Estado inicial de M .	1
${\ Displaystyle H_ {0,0}}$		Posición inicial del cabezal de lectura / escritura.	1
${\ Displaystyle \ neg T_ {i, j, k} \ lor \ neg T_ {i, j ', k}}$	j ≠ j ′	Como máximo, un símbolo por celda de cinta.	O ( p ( n ) ² )
${\ Displaystyle \ bigvee _ {j \ in \ Sigma} T_ {i, j, k}}$		Al menos un símbolo por celda de cinta.	O ( p ( n ) ² )
${\ Displaystyle T_ {i, j, k} \ land T_ {i, j ', k + 1} \ rightarrow H_ {i, k}}$	j ≠ j ′	La cinta permanece sin cambios a menos que esté escrita.	O ( p ( n ) ² )
¬ 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 ) ³ )
${\ Displaystyle {\ begin {array} {l} (H_ {i, k} \ land Q_ {q, k} \ land T_ {i, \ sigma, k}) \ to \\\ bigvee _ {((q , \ sigma), (q ', \ sigma', d)) \ in \ delta} (H_ {i + d, \ k + 1} \ land Q_ {q ', \ k + 1} \ land T_ {i , \ \ sigma ', \ k + 1}) \ end {matriz}}}$	k < p ( n )	Posibles transiciones en el paso de cálculo k cuando la cabeza está en la posición i .	O ( p ( n ) ² )
${\ Displaystyle \ bigvee _ {0 \ leq k \ leq p (n)} \ bigvee _ {f \ in F} Q_ {f, k}}$		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 es satisfactorio 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 ) ² ) variables booleanas, cada una codificable en el espacio $O (log p (n))$ . El número de cláusulas es O ( p ( n ) ³ ) por lo que el tamaño de B es O (log ( p ( n )) p ( n ) ³ ). Por lo tanto, la transformación es ciertamente una reducción de muchos uno en tiempo polinómico, según se requiera.

Complejidad

Mientras que el método anterior codifica una máquina de Turing no determinista en complejidad , la literatura describe enfoques más sofisticados en complejidad . El resultado cuasilineal apareció por primera vez siete años después de la publicación original de Cook. ${\ Displaystyle O (log (p (n)) p (n) ^ {3})}$ ${\ Displaystyle O (p (n) log (p (n)))}$

Las versiones generalizadas de la satisfacibilidad booleana tienen codificaciones con límites aún más fuertes: las fórmulas booleanas cuantificadas (QBF) codifican máquinas de Turing no deterministas en complejidad polinomial para el espacio limitado de la máquina (en oposición al límite de tiempo), y las fórmulas booleanas cuantificadas de dependencia (DQBF) codifican no -máquinas de Turing deterministas en una complejidad logarítmica ideal para el espacio de la máquina.

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.

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 , 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 polinómico 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 .

Languages

In other projects