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 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 booleano de satisfacibilidad.
Una consecuencia importante de este teorema es que si existe un algoritmo determinista de tiempo polinomial para resolver la satisfacibilidad booleana, entonces cada 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 lo tanto, equivalente al problema P versus NP , que se considera ampliamente el problema sin resolver más importante en la informática teórica.
El concepto de NP-completo fue desarrollado a fines de la década de 1960 y principios de la de 1970 en paralelo por investigadores en América del Norte y la URSS . En 1971, Stephen Cook publicó su artículo "La complejidad de los procedimientos de prueba de teoremas" [1] 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", [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, en 1975, que resolver 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 complejidad temporal deterministas subexponenciales 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] Más tarde , 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 fue ligeramente diferente del 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 problemas de búsqueda NP-completos de este tipo, o problemas universales . Además, encontró para cada uno de estos problemas un algoritmo que lo resuelve en un tiempo óptimo (en particular, estos algoritmos se ejecutan en tiempo polinomial si y solo si P = NP ).
