Teorema de Cook-Levin

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 booleana es NP-completo . Es decir, pertenece a NP , y cualquier problema en NP puede reducirse en tiempo polinomial mediante una máquina de Turing determinista al problema de satisfacibilidad booleana.

El teorema recibe su nombre de Stephen Cook y Leonid Levin . La demostración se debe a Richard Karp , basada en una demostración anterior (que utiliza una noción diferente de reducibilidad) de Cook. ^{[ 1 ]}

Una consecuencia importante de este teorema es que, si existe un algoritmo determinista de tiempo polinomial para resolver la satisfacibilidad booleana, entonces todo problema NP puede resolverse mediante un algoritmo determinista de tiempo polinomial. La cuestión de si existe tal algoritmo para la satisfacibilidad booleana es, por lo tanto, equivalente al problema P versus NP , que aún se considera el problema sin resolver más importante en la informática teórica .

El concepto de NP-completitud fue desarrollado a finales de la década de 1960 y principios de la de 1970 de forma paralela por investigadores de Norteamérica y la Unión Soviética . En 1971, Stephen Cook publicó su artículo «La complejidad de los procedimientos de demostración de teoremas» ^{[ 2 ]} en las actas del recién fundado Simposio ACM sobre Teoría de la Computación . El artículo posterior de Richard Karp , «Reducibilidad entre problemas combinatorios» ^{[ 1 ],} generó un renovado interés en el artículo de Cook al proporcionar una lista de 21 problemas NP-completos . Karp también introdujo la noción de completitud utilizada en la definición actual de NP-completitud (es decir, mediante reducción de muchos a uno en tiempo polinomial ). Tanto Cook como Karp recibieron el Premio Turing por este trabajo.

El interés teórico en la NP-completitud también se vio reforzado por el trabajo de Theodore P. Baker, John Gill y Robert Solovay, quienes demostraron, en 1975, que resolver problemas NP en ciertos modelos de máquinas oráculo requiere tiempo exponencial. Es decir, existe un oráculo A tal que, para todas las clases de complejidad determinista subexponencial T, la clase de complejidad relativizada NP ^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 universales", ^{[ 5 ]} se publicó en 1973, aunque se mencionó en charlas y se presentó para su publicación unos años antes.

El enfoque de Levin difería ligeramente del de Cook y Karp, ya que consideraba problemas de búsqueda que requieren encontrar soluciones en lugar de simplemente determinar su existencia. Propuso seis problemas de búsqueda NP-completos, o problemas universales . Además, halló para cada uno de estos problemas un algoritmo que lo resuelve en tiempo óptimo (en particular, estos algoritmos se ejecutan en tiempo polinomial si y solo si P = NP ).

Un problema de decisión pertenece a NP si puede ser resuelto por una máquina de Turing no determinista en tiempo polinomial .

Un ejemplo del problema de satisfacibilidad booleana es una expresión booleana que combina variables booleanas mediante operadores booleanos . Dicha expresión es satisfacible si existe alguna asignación de valores de verdad a las variables que haga que la expresión completa sea verdadera.

Dado cualquier problema de decisión en NP, se construye una máquina no determinista que lo resuelve en tiempo polinomial. Luego, para cada entrada de dicha máquina, se construye una expresión booleana que calcula si, al recibir esa entrada específica, la máquina se ejecuta correctamente y se detiene respondiendo "sí". La expresión se satisface si y solo si existe una forma de que la máquina se ejecute correctamente y responda "sí". Por lo tanto, la satisfacibilidad de la expresión construida equivale a preguntar si la máquina responderá "sí" o no.

Esta demostración se basa en la presentada por Garey y Johnson en 1979 , págs. 38-44, Sección 2.6 . 

Demostrar que el problema de satisfacibilidad booleana (SAT) es NP-completo consta de dos partes. Una consiste en demostrar que SAT es un problema NP. La otra consiste en demostrar que todo problema NP puede reducirse a una instancia de un problema SAT mediante una reducción de muchos a uno en tiempo polinomial .

SAT pertenece a NP porque cualquier asignación de valores booleanos a variables booleanas que se afirme que satisface la expresión dada puede verificarse en tiempo polinomial mediante una máquina de Turing determinista. (Las afirmaciones verificables en tiempo polinomial por una máquina de Turing determinista y resolubles en tiempo polinomial por una máquina de Turing no determinista son equivalentes, y la demostración puede encontrarse en muchos libros de texto, por ejemplo, en la sección 7.3 de Introduction to the Theory of Computation de Sipser , así como en el artículo de Wikipedia sobre NP ).

Ahora supongamos que un problema dado en NP puede ser resuelto por la máquina de Turing no determinista.${\displaystyle M=(Q,\Sigma ,s,F,\delta )}$, dónde${\displaystyle Q}$es el conjunto de estados,${\displaystyle \Sigma }$es el alfabeto de símbolos de cinta,${\displaystyle s\in Q}$es el estado inicial,${\displaystyle F\subseteq Q}$es el conjunto de estados que aceptan y${\displaystyle \delta \subseteq ((Q\setminus F)\times \Sigma )\times (Q\times \Sigma \times \{-1,+1\})}$es la relación de transición. Supongamos además que${\displaystyle M}$acepta o rechaza una instancia del problema después de como máximo${\displaystyle p(n)}$pasos de cálculo, donde${\displaystyle n}$es el tamaño de la instancia y${\displaystyle p}$es una función polinómica.

Para cada entrada,${\displaystyle I}$, especifique una expresión booleana${\displaystyle B}$que es satisfacible si y solo si la máquina${\displaystyle M}$acepta${\displaystyle I}$.

La expresión booleana utiliza las variables que se muestran en la siguiente tabla. Aquí,${\displaystyle q\in Q}$es un estado de máquina,${\displaystyle -p(n)\leq i\leq p(n)}$es una posición de cinta,${\displaystyle j\in \Sigma }$es un símbolo de cinta, y${\displaystyle 0\leq k\leq p(n)}$es el número de un paso de cálculo.

Defina la expresión booleana${\displaystyle B}$ser la conjunción de las subexpresiones en la siguiente tabla, para todo${\displaystyle -p(n)\leq i\leq p(n)}$y${\displaystyle 0\leq k\leq p(n)}$:

Si existe un cálculo de aceptación para${\displaystyle M}$en la entrada${\displaystyle I}$, entonces${\displaystyle B}$es satisfecha mediante la asignación${\displaystyle T_{i,j,k}}$,${\displaystyle H_{i,k}}$y${\displaystyle Q_{i,k}}$sus interpretaciones previstas. Por otro lado, si${\displaystyle B}$es satisfacible, entonces hay un cálculo de aceptación para${\displaystyle M}$en la entrada${\displaystyle I}$que sigue los pasos indicados por las asignaciones a las variables.

Hay${\displaystyle O(p(n)^{2})}$Variables booleanas, cada una codificable en el espacio${\displaystyle O(\log p(n))}$. El número de cláusulas es${\displaystyle O(p(n)^{3})}$^{[ 7 ]} por lo que el tamaño de${\displaystyle B}$es${\displaystyle O(\log(p(n))p(n)^{3})}$. Por lo tanto, la transformación es ciertamente una reducción de muchos a uno en tiempo polinomial, como se requiere.

Solo la primera fila de la tabla (${\displaystyle T_{i,j,0}}$) en realidad depende de la cadena de entrada${\displaystyle I}$Las líneas restantes dependen únicamente de la longitud de entrada.${\displaystyle n}$y en la máquina${\displaystyle M}$; formalizan un cálculo genérico de${\displaystyle M}$hasta${\displaystyle p(n)}$pasos.

La transformación hace un uso extensivo del polinomio${\displaystyle p(n)}$. En consecuencia, la demostración anterior no es constructiva : incluso si${\displaystyle M}$Se sabe que, al observar la pertenencia del problema dado a NP, la transformación no se puede calcular de manera efectiva, a menos que se conozca un límite superior.${\displaystyle p(n)}$de${\displaystyle M}$También se conoce su complejidad temporal.

Si bien el método anterior codifica una máquina de Turing no determinista en complejidad${\displaystyle O(\log(p(n))p(n)^{3})}$La literatura describe enfoques más sofisticados en cuanto a complejidad.${\displaystyle O(p(n)\log(p(n)))}$. ^{[ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ]} El resultado cuasilineal apareció por primera vez siete años después de la publicación original de Cook.

El uso de SAT para demostrar la existencia de un problema NP-completo puede extenderse a otros problemas computacionales en lógica y a la completitud para otras clases de complejidad . El problema de la fórmula booleana cuantificada (QBF) involucra fórmulas booleanas extendidas para incluir cuantificadores universales anidados y cuantificadores existenciales para sus variables. El problema QBF puede usarse para codificar la computación con una máquina de Turing limitada a la complejidad espacial polinomial , demostrando que existe un problema (el reconocimiento de fórmulas booleanas cuantificadas verdaderas) que es PSPACE-completo . Análogamente, las fórmulas booleanas cuantificadas de dependencia codifican la computación con una máquina de Turing limitada a la complejidad espacial logarítmica , demostrando que existe un problema que es NL-completo . ^{[ 13 ] [ 14 ]}

La demostración muestra que cada problema en NP puede reducirse en tiempo polinomial (de hecho, basta con espacio logarítmico ) a una instancia del problema de satisfacibilidad booleana. Esto significa que si el problema de satisfacibilidad booleana pudiera resolverse en tiempo polinomial mediante una máquina de Turing determinista , entonces todos los problemas en NP podrían resolverse en tiempo polinomial, y por lo tanto la clase de complejidad NP sería igual a la clase de complejidad P.

La importancia de la NP-completitud quedó clara con la publicación en 1972 del artículo fundamental de Richard Karp , "Reducibilidad entre problemas combinatorios", en el que demostró que 21 problemas diversos de combinatoria y teoría de grafos , cada uno tristemente célebre por su intratabilidad, son NP-completos. ^{[ 1 ]}

Karp demostró que cada uno de sus problemas era NP-completo al reducir otro problema (que ya se había demostrado que era NP-completo) a ese problema. Por ejemplo, demostró que el problema 3SAT (el problema de satisfacibilidad booleana para expresiones en forma normal conjuntiva (FNC) con exactamente tres variables o negaciones de variables por cláusula) era NP-completo al mostrar cómo reducir (en tiempo polinomial) cualquier instancia de SAT a una instancia equivalente de 3SAT. ^{[ 15 ]}

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 [ ^{16 ] y} aún se siguen descubriendo nuevos problemas que se encuentran dentro de esa clase de complejidad.

Aunque muchos casos prácticos del problema SAT pueden resolverse mediante métodos heurísticos , la cuestión de si existe un algoritmo determinista de tiempo polinomial para SAT (y, por consiguiente, para todos los demás problemas NP-completos) sigue siendo un problema famoso sin resolver, a pesar de décadas de intensos esfuerzos por parte de teóricos de la complejidad, lógicos matemáticos y otros. Para más detalles, véase el artículo «El problema P frente al problema NP» .