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 determinista de Turing al problema de satisfacibilidad booleana.
El teorema lleva el nombre de Stephen Cook y Leonid Levin . La prueba se debe a Richard Karp , basada en una prueba anterior (usando 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 todavía se considera ampliamente como el problema sin resolver más importante en la informática teórica .
El concepto de completitud NP fue desarrollado a finales de los años 1960 y principios de los 1970 en paralelo 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" [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 interés renovado 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 completitud NP (es decir, por reducción de muchos uno en tiempo polinomial ). Cook y Karp recibieron cada uno 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 resolver problemas de NP en ciertos modelos de máquinas Oracle requiere un 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 ≠ NPA . [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 fue mencionado en charlas y presentado para su publicación unos años antes.
El enfoque de Levin era ligeramente diferente del de Cook y Karp en que consideraba problemas de búsqueda , que requieren encontrar soluciones en lugar de simplemente determinar la existencia. Proporcionó 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 el tiempo óptimo (en particular, estos algoritmos se ejecutan en tiempo polinómico si y sólo si P = NP ).
Un problema de decisión está en NP si puede resolverse mediante 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 . Tal expresión es satisfactoria si hay 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, cree una expresión booleana que calcule si cuando esa entrada específica se pasa a la máquina, la máquina funciona correctamente, se detiene y responde "sí". Entonces la expresión puede satisfacerse si y sólo si hay una manera de que la máquina funcione correctamente y responda "sí", por lo que la satisfacibilidad de la expresión construida equivale a preguntar si la máquina responderá "sí" o no.
Esta prueba se basa en la proporcionada por Garey y Johnson 1979, págs. 38–44, sección 2.6.
Hay dos partes para demostrar que el problema booleano de satisfacibilidad (SAT) es NP completo. Una es demostrar que el SAT es un problema NP. La otra es mostrar que cada 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 determinista de Turing. (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 ).
Ahora supongamos que un problema dado en NP puede resolverse mediante 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 se acepta o rechaza una instancia del problema después de como máximo los 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 sólo si la máquina acepta .
La expresión booleana utiliza las variables establecidas en la siguiente tabla. Aquí, es el estado de la máquina, es la posición de la cinta, es el símbolo de la cinta y es el número de un paso de cálculo.
Defina la expresión booleana como la conjunción de las subexpresiones en la siguiente tabla, para todos y :
Si hay un cálculo de aceptación para la entrada , entonces se puede satisfacer asignando y sus interpretaciones previstas. Por otro lado, si es satisfactoria, entonces hay un cálculo de aceptación de 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 polinomial, según sea necesario.
Sólo la primera fila de la tabla ( ) depende realmente de la cadena de entrada . Las líneas restantes dependen sólo de la longitud de entrada y de la máquina ; formalizan un cómputo genérico de hasta pasos.
La transformación hace un uso extensivo del polinomio . Como consecuencia, la prueba anterior no es constructiva : incluso si se conoce, teniendo en cuenta 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 demostrar 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) implica fórmulas booleanas ampliadas para incluir cuantificadores universales anidados y cuantificadores existenciales para sus variables. El problema QBF se puede utilizar para codificar cálculos con una máquina de Turing limitada a la complejidad del espacio polinomial , demostrando que existe un problema (el reconocimiento de fórmulas booleanas cuantificadas verdaderas) que es PSPACE completo . De manera análoga, las fórmulas booleanas cuantificadas por 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 todo problema en NP se puede reducir en tiempo polinomial (de hecho, el espacio logarítmico es suficiente) a una instancia del problema de satisfacibilidad booleana. Esto significa que si el problema booleano de satisfacibilidad pudiera resolverse en tiempo polinómico mediante una máquina de Turing determinista , entonces todos los problemas en NP podrían resolverse en tiempo polinómico, por lo que la clase de complejidad NP sería igual a la clase de complejidad P.
La importancia de la completitud NP quedó clara con la publicación en 1972 del artículo histórico de Richard Karp , "Reducibilidad entre problemas combinatorios", en el que demostró que 21 problemas diversos de teoría combinatoria y de grafos , cada uno de ellos infame por su intratabilidad, son NP. -completo. [1]
Karp demostró que cada uno de sus problemas era NP-completo reduciendo otro problema (que ya se había demostrado que era NP-completo) a ese problema. Por ejemplo, demostró que el problema 3SAT (el problema booleano de satisfacibilidad para expresiones en forma normal conjuntiva (CNF) con exactamente tres variables o negaciones de variables por cláusula) es 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 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 .
