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, es NP y cualquier problema en NP puede reducirse en tiempo polinómico mediante una máquina de Turing determinista al problema de satisfacibilidad booleano.
El teorema recibe su nombre de Stephen Cook y Leonid Levin . La prueba se debe a Richard Karp , basada en una prueba 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 un algoritmo de este tipo para la satisfacibilidad booleana es, por tanto, equivalente al problema P versus NP , que todavía se considera ampliamente el problema sin resolver más importante en la informática teórica .
El concepto de NP-completitud fue desarrollado a finales de los años 1960 y principios de los años 1970 en paralelo 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 de la conferencia 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, por reducción de muchos a uno en tiempo polinomial ). Cook y Karp recibieron cada uno un premio Turing por este trabajo.
El interés teórico en la completitud NP también fue mejorado 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 de tiempo 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 universal", [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 era ligeramente diferente al de Cook y Karp, ya que consideró problemas de búsqueda , que requieren encontrar soluciones en lugar de simplemente determinar la existencia. Propuso seis 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 tiempo óptimo (en particular, estos algoritmos se ejecutan en tiempo polinomial si y solo si P = NP ).
Un problema de decisión es 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 . Una expresión de este tipo es satisfacible si existe alguna asignación de valores de verdad a las variables que haga que toda la expresión sea verdadera.
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 cuando esa entrada específica se pasa a la máquina, la máquina funciona correctamente y 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 satisfacibilidad de la expresión construida es equivalente a preguntar si la máquina responderá "sí" o no.
Esta prueba se basa en la dada por Garey & Johnson 1979, pp. 38–44, Sección 2.6.
Hay dos partes para demostrar que el problema de satisfacibilidad booleano (SAT) es NP-completo. Una es demostrar que SAT es un problema NP. La otra es demostrar que todo problema NP se puede reducir a una instancia de un problema SAT mediante una reducción de muchos-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 polinomial mediante una máquina de Turing determinista. (Las afirmaciones verificables en tiempo polinomial mediante una máquina de Turing determinista y resolubles en tiempo polinomial mediante una máquina de Turing no determinista son equivalentes, y la prueba 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 ).
Supongamos ahora que un problema dado en NP puede ser resuelto por la máquina de Turing no determinista , donde es el conjunto de estados, es el alfabeto de símbolos de cinta, es el estado inicial, es el conjunto de estados de aceptación y es la relación de transición. Supongamos además que acepta o rechaza una instancia del problema después de, como máximo, pasos de cálculo, donde es el tamaño de la instancia y es una función polinómica.
Para cada entrada, , especifique una expresión booleana que sea satisfactoria si y solo si la máquina acepta .
La expresión booleana utiliza las variables que se indican en la siguiente tabla. Aquí, es un estado de la máquina, es una posición de cinta, es un símbolo de cinta y es el número de un paso de cálculo.
Defina la expresión booleana como la conjunción de las subexpresiones de la siguiente tabla, para todos y :
Si hay un cálculo de aceptación para en la entrada , entonces es satisfacible mediante la asignación y sus interpretaciones previstas. Por otro lado, si es satisfacible, entonces hay un cálculo de aceptación para en la entrada que sigue los pasos indicados por las asignaciones a las variables.
Hay variables booleanas, cada una codificable en el espacio . El número de cláusulas es [7], por lo que el tamaño de es . Por lo tanto, la transformación es ciertamente una reducción de muchos a uno en tiempo polinómico, como se requiere.
En realidad, solo la primera fila de la tabla ( ) depende de la cadena de entrada . Las líneas restantes dependen solo de la longitud de entrada y de la máquina ; formalizan un cálculo genérico de hasta pasos.
La transformación hace un uso extensivo del polinomio . En consecuencia, la prueba anterior no es constructiva : incluso si se conoce , al observar la pertenencia del problema dado a NP, la transformación no se puede calcular de manera efectiva, a menos que también se conozca un límite superior de la complejidad temporal de .
Si bien el método anterior codifica una máquina de Turing no determinista en complejidad , la literatura describe enfoques más sofisticados en complejidad . [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 probar la existencia de un problema NP-completo se puede extender a otros problemas computacionales en lógica, y a la completitud para otras clases de complejidad . El problema de fórmula booleana cuantificada (QBF) involucra fórmulas booleanas extendidas para incluir cuantificadores universales anidados y cuantificadores existenciales para sus variables. El problema QBF se puede utilizar para codificar el cálculo con una máquina de Turing limitada a la complejidad del espacio polinomial , lo que demuestra 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 el cálculo con una máquina de Turing limitada a la complejidad del espacio logarítmico , lo que demuestra que existe un problema que es NL-completo . [13] [14]
La prueba muestra que cada problema en NP puede ser reducido en tiempo polinómico (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 ser resuelto en tiempo polinómico mediante una máquina de Turing determinista , entonces todos los problemas en NP podrían ser resueltos en tiempo polinómico, 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 combinatorios y teóricos de grafos diversos , cada uno famoso 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 booleano para expresiones en forma normal conjuntiva (CNF) 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 todavía se están descubriendo nuevos problemas que están dentro de esa clase de complejidad.
Aunque muchos casos prácticos 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, para todos los demás problemas NP-completos) sigue siendo un famoso problema 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 .
