El problema de satisfacibilidad booleano (SAT) pretende determinar si una fórmula proposicional (ejemplo representado) puede hacerse verdadera mediante una asignación apropiada ("solución") de valores de verdad a sus variables. Si bien es fácil verificar si una asignación dada hace que la fórmula sea verdadera , [1] no se conoce ningún método esencialmente más rápido para encontrar una asignación satisfactoria que probar todas las asignaciones en sucesión. Cook y Levin demostraron que cada problema fácil de verificar puede resolverse tan rápido como SAT, que, por lo tanto, es NP-completo.
Es un problema de decisión , lo que significa que para cualquier entrada al problema, la salida es "sí" o "no".
Cuando la respuesta es "sí", esto se puede demostrar mediante la existencia de una solución corta (longitud polinómica) .
La exactitud de cada solución se puede verificar rápidamente (es decir, en tiempo polinomial ) y un algoritmo de búsqueda de fuerza bruta puede encontrar una solución probando todas las soluciones posibles.
El problema puede utilizarse para simular cualquier otro problema cuya solución sea correcta de forma rápida. En este sentido, los problemas NP-completos son los más difíciles de aquellos cuyas soluciones se pueden verificar rápidamente. Si pudiéramos encontrar soluciones de algún problema NP-completo rápidamente, podríamos encontrar rápidamente las soluciones de cualquier otro problema cuya solución dada se pueda verificar fácilmente.
El nombre "NP-completo" es la abreviatura de "completo en tiempo polinomial no determinista". En este nombre, "no determinista" se refiere a las máquinas de Turing no deterministas , una forma de formalizar matemáticamente la idea de un algoritmo de búsqueda de fuerza bruta. El tiempo polinomial se refiere a una cantidad de tiempo que se considera "rápida" para que un algoritmo determinista verifique una única solución, o para que una máquina de Turing no determinista realice toda la búsqueda. " Completo " se refiere a la propiedad de poder simular todo en la misma clase de complejidad .
Más precisamente, cada entrada al problema debe estar asociada con un conjunto de soluciones de longitud polinómica, la validez de cada una de las cuales puede probarse rápidamente (en tiempo polinómico ), [2] de modo que la salida para cualquier entrada sea "sí" si el conjunto de soluciones no está vacío y "no" si está vacío. La clase de complejidad de los problemas de esta forma se llama NP , una abreviatura de "tiempo polinómico no determinista". Se dice que un problema es NP-duro si todo en NP puede transformarse en él en tiempo polinómico aunque no esté en NP. Un problema es NP-completo si está tanto en NP como NP-duro. Los problemas NP-completos representan los problemas más difíciles en NP. Si algún problema NP-completo tiene un algoritmo de tiempo polinómico, todos los problemas en NP lo tienen. El conjunto de problemas NP-completos a menudo se denota por NP-C o NPC .
Aunque la solución de un problema NP-completo se puede verificar "rápidamente", no se conoce ninguna forma de encontrar una solución rápidamente. Es decir, el tiempo necesario para resolver el problema utilizando cualquier algoritmo conocido aumenta rápidamente a medida que crece el tamaño del problema. En consecuencia, determinar si es posible resolver estos problemas rápidamente, llamado el problema P versus NP , es uno de los problemas fundamentales sin resolver en la informática actual.
Los problemas NP-completos están en NP , el conjunto de todos los problemas de decisión cuyas soluciones pueden verificarse en tiempo polinomial; NP puede definirse de manera equivalente como el conjunto de problemas de decisión que pueden resolverse en tiempo polinomial en una máquina de Turing no determinista . Un problema p en NP es NP-completo si todos los demás problemas en NP pueden transformarse (o reducirse) en p en tiempo polinomial. [ cita requerida ]
No se sabe si todos los problemas en NP pueden resolverse rápidamente; esto se llama el problema P versus NP . Pero si cualquier problema NP-completo puede resolverse rápidamente, entonces todos los problemas en NP pueden resolverse, porque la definición de un problema NP-completo establece que cada problema en NP debe ser rápidamente reducible a cualquier problema NP-completo (es decir, puede reducirse en tiempo polinomial). Debido a esto, a menudo se dice que los problemas NP-completos son más difíciles que los problemas NP en general. [ cita requerida ]
Definición formal
Un problema de decisión es NP-completo si: [ cita necesaria ]
está en NP, y
Todo problema en NP es reducible a tiempo polinomial. [3]
Se puede demostrar que está en NP demostrando que una solución candidata a puede verificarse en tiempo polinomial.
Téngase en cuenta que un problema que satisface la condición 2 se dice que es NP-difícil , independientemente de que satisfaga o no la condición 1. [4]
Una consecuencia de esta definición es que si tuviéramos un algoritmo de tiempo polinomial (en una UTM o cualquier otra máquina abstracta equivalente a Turing ) para , podríamos resolver todos los problemas en NP en tiempo polinomial.
Fondo
Diagrama de Euler para conjuntos de problemas P , NP , NP-completos y NP-difíciles . El lado izquierdo es válido bajo el supuesto de que P≠NP , mientras que el lado derecho es válido bajo el supuesto de que P=NP (excepto que el lenguaje vacío y su complemento nunca son NP-completos y, en general, no todos los problemas en P o NP son NP-completos).
El concepto de NP-completitud se introdujo en 1971 (véase el teorema de Cook-Levin ), aunque el término NP-completo se introdujo más tarde. En la conferencia STOC de 1971 , hubo un intenso debate entre los científicos informáticos sobre si los problemas NP-completos se podían resolver en tiempo polinómico en una máquina de Turing determinista . John Hopcroft llevó a todos los presentes en la conferencia a un consenso de que la cuestión de si los problemas NP-completos se pueden resolver en tiempo polinómico debería posponerse para su resolución en una fecha posterior, ya que nadie tenía pruebas formales de sus afirmaciones en un sentido u otro. [ cita requerida ] Esto se conoce como "la cuestión de si P = NP".
Nadie ha podido determinar de manera concluyente si los problemas NP-completos son de hecho solucionables en tiempo polinómico, lo que convierte a este en uno de los grandes problemas sin resolver de las matemáticas . El Instituto Clay de Matemáticas ofrece una recompensa de un millón de dólares ( Premio del Milenio ) a quien tenga una prueba formal de que P=NP o de que P≠NP. [5]
La existencia de problemas NP-completos no es obvia. El teorema de Cook-Levin establece que el problema de satisfacibilidad booleano es NP-completo, estableciendo así que tales problemas existen. En 1972, Richard Karp demostró que varios otros problemas también eran NP-completos (ver los 21 problemas NP-completos de Karp ); por lo tanto, existe una clase de problemas NP-completos (además del problema de satisfacibilidad booleano). Desde los resultados originales, se ha demostrado que miles de otros problemas son NP-completos mediante reducciones de otros problemas que previamente se habían demostrado que eran NP-completos; muchos de estos problemas están recopilados en Garey & Johnson (1979).
Problemas NP-completos
Algunos problemas NP-completos, que indican las reducciones que se utilizan normalmente para demostrar su NP-completitud
La forma más sencilla de demostrar que un nuevo problema es NP-completo es demostrar primero que es NP y luego reducir a él algún problema NP-completo conocido. Por lo tanto, resulta útil conocer una variedad de problemas NP-completos. La lista siguiente contiene algunos problemas conocidos que son NP-completos cuando se expresan como problemas de decisión.
A la derecha se muestra un diagrama de algunos de los problemas y las reducciones que se suelen utilizar para demostrar su carácter NP-completo. En este diagrama, los problemas se reducen de abajo hacia arriba. Nótese que este diagrama es engañoso como descripción de la relación matemática entre estos problemas, ya que existe una reducción en tiempo polinómico entre dos problemas NP-completos cualesquiera; pero indica dónde ha sido más fácil demostrar esta reducción en tiempo polinómico.
A menudo, hay solo una pequeña diferencia entre un problema en P y un problema NP-completo. Por ejemplo, el problema de 3-satisfacibilidad , una restricción del problema de satisfacibilidad booleano, sigue siendo NP-completo, mientras que el problema de 2-satisfacibilidad, ligeramente más restringido, está en P (específicamente, es NL-completo ), pero el problema de 2-sat. máx., ligeramente más general, es nuevamente NP-completo. Determinar si un grafo se puede colorear con 2 colores está en P, pero con 3 colores es NP-completo, incluso cuando se restringe a grafos planares . Determinar si un grafo es un ciclo o es bipartito es muy fácil (en L ), pero encontrar un subgrafo máximo bipartito o de ciclo máximo es NP-completo. Una solución del problema de la mochila dentro de cualquier porcentaje fijo de la solución óptima se puede calcular en tiempo polinomial, pero encontrar la solución óptima es NP-completo.
Isomorfismo de gráficos: ¿el gráfico G 1 es isomorfo al gráfico G 2 ?
Isomorfismo de subgrafos: ¿el grafo G 1 es isomorfo a un subgrafo del grafo G 2 ?
El problema de isomorfismo de subgrafos es NP-completo. Se sospecha que el problema de isomorfismo de grafos no está en P ni en NP-completo, aunque sí está en NP. Este es un ejemplo de un problema que se considera difícil , pero que no se considera NP-completo. Esta clase se denomina problemas NP-intermedios y existe si y solo si P≠NP.
Solución de problemas NP-completos
En la actualidad, todos los algoritmos conocidos para problemas NP-completos requieren un tiempo de entrada superpolinomial . El problema de la cobertura de vértices tiene [6] para algunos y se desconoce si existen algoritmos más rápidos.
Las siguientes técnicas se pueden aplicar para resolver problemas computacionales en general y a menudo dan lugar a algoritmos sustancialmente más rápidos:
Aproximación : en lugar de buscar una solución óptima, busque una solución que sea, como máximo, un factor de una óptima.
Aleatorización : utilizar la aleatoriedad para obtener un tiempo de ejecución promedio más rápido y permitir que el algoritmo falle con una pequeña probabilidad. Nota: el método de Monte Carlo no es un ejemplo de un algoritmo eficiente en este sentido específico, aunque los enfoques evolutivos como los algoritmos genéticos pueden serlo.
Restricción: al restringir la estructura de la entrada (por ejemplo, a gráficos planares), generalmente son posibles algoritmos más rápidos.
Parametrización : A menudo existen algoritmos rápidos si ciertos parámetros de la entrada son fijos.
Heurística : Algoritmo que funciona "razonablemente bien" en muchos casos, pero para el cual no hay pruebas de que sea siempre rápido y produzca siempre un buen resultado. A menudo se utilizan métodos metaheurísticos .
Un ejemplo de un algoritmo heurístico es un algoritmo de coloración voraz subóptimo utilizado para colorear gráficos durante la fase de asignación de registros de algunos compiladores, una técnica llamada asignación global de registros para colorear gráficos . Cada vértice es una variable, se dibujan bordes entre las variables que se están utilizando al mismo tiempo y los colores indican el registro asignado a cada variable. Debido a que la mayoría de las máquinas RISC tienen una cantidad bastante grande de registros de propósito general, incluso un enfoque heurístico es efectivo para esta aplicación.
Completitud bajo diferentes tipos de reducción
En la definición de NP-completo dada anteriormente, el término reducción se utilizó en el significado técnico de una reducción de muchos a uno en tiempo polinomial .
Otro tipo de reducción es la reducción de Turing en tiempo polinómico . Un problema es reducible en tiempo polinómico a un problema de Turing si, dada una subrutina que se resuelve en tiempo polinómico, se puede escribir un programa que llame a esta subrutina y la resuelva en tiempo polinómico. Esto contrasta con la reducibilidad de muchos a uno, que tiene la restricción de que el programa solo puede llamar a la subrutina una vez y el valor de retorno de la subrutina debe ser el valor de retorno del programa.
Si uno define el análogo a NP-completo con reducciones de Turing en lugar de reducciones de muchos-uno, el conjunto de problemas resultante no será más pequeño que NP-completo; es una pregunta abierta si será más grande.
Otro tipo de reducción que también se utiliza a menudo para definir la NP-completitud es la reducción de muchos-uno en el espacio logarítmico , que es una reducción de muchos-uno que se puede calcular con solo una cantidad logarítmica de espacio. Dado que cada cálculo que se puede hacer en el espacio logarítmico también se puede hacer en tiempo polinomial, se deduce que si hay una reducción de muchos-uno en el espacio logarítmico, entonces también hay una reducción de muchos-uno en tiempo polinomial. Este tipo de reducción es más refinada que las reducciones de muchos-uno en tiempo polinomial más habituales y nos permite distinguir más clases como P-completo . Si bajo estos tipos de reducciones cambia la definición de NP-completo sigue siendo un problema abierto. Todos los problemas NP-completos conocidos actualmente son NP-completos bajo reducciones del espacio logarítmico. Todos los problemas NP-completos conocidos actualmente siguen siendo NP-completos incluso bajo reducciones mucho más débiles, como reducciones y reducciones. Se sabe que algunos problemas NP-completos, como SAT, son completos incluso bajo proyecciones de tiempo polilogarítmico. [7] Sin embargo, se sabe que las reducciones AC definen una clase estrictamente más pequeña que las reducciones de tiempo polinomial. [8]
Nombramiento
Según Donald Knuth , el nombre "NP-completo" fue popularizado por Alfred Aho , John Hopcroft y Jeffrey Ullman en su célebre libro de texto "El diseño y análisis de algoritmos informáticos". Informa que introdujeron el cambio en las pruebas de galerada para el libro (de "polinomio-completo"), de acuerdo con los resultados de una encuesta que había realizado en la comunidad de informática teórica . [9] Otras sugerencias hechas en la encuesta [10] incluyeron " hercúleo ", "formidable", el "duro" de Steiglitz en honor a Cook y el acrónimo "PET" de Shen Lin, que significaba "tiempo probablemente exponencial", pero que dependiendo de la dirección en que se desarrollara el problema P versus NP , podría significar "tiempo demostrablemente exponencial" o "tiempo previamente exponencial". [11]
Conceptos erróneos comunes
Los siguientes conceptos erróneos son frecuentes: [12]
"Los problemas NP-completos son los problemas conocidos más difíciles". Como los problemas NP-completos están en NP, su tiempo de ejecución es, como mucho, exponencial. Sin embargo, se ha demostrado que algunos problemas requieren más tiempo, por ejemplo, la aritmética de Presburger . De algunos problemas, incluso se ha demostrado que nunca se pueden resolver en absoluto, por ejemplo, el problema de la parada .
"Los problemas NP-completos son difíciles porque hay muchas soluciones diferentes". Por un lado, hay muchos problemas que tienen un espacio de soluciones igual de grande, pero que se pueden resolver en tiempo polinomial (por ejemplo, árbol de expansión mínima ). Por otro lado, hay problemas NP con una única solución como máximo que son NP-difíciles en una reducción aleatoria en tiempo polinomial (véase el teorema de Valiant-Vazirani ).
"Resolver problemas NP-completos requiere tiempo exponencial". En primer lugar, esto implicaría que P ≠ NP, lo que sigue siendo una cuestión sin resolver. Además, algunos problemas NP-completos en realidad tienen algoritmos que se ejecutan en tiempo superpolinomial, pero subexponencial, como O(2 √ n n ). Por ejemplo, los problemas de conjunto independiente y conjunto dominante para grafos planares son NP-completos, pero se pueden resolver en tiempo subexponencial utilizando el teorema del separador planar . [13]
"Cada instancia de un problema NP-completo es difícil". A menudo, algunas instancias, o incluso la mayoría de las instancias, pueden ser fáciles de resolver en tiempo polinomial. Sin embargo, a menos que P=NP, cualquier algoritmo en tiempo polinomial debe estar equivocado asintóticamente en más de un número polinomial de las muchas entradas exponenciales de un cierto tamaño. [14]
"Si P=NP, todos los códigos criptográficos pueden ser descifrados". Un problema de tiempo polinómico puede ser muy difícil de resolver en la práctica si el grado o las constantes del polinomio son lo suficientemente grandes. Además, la seguridad basada en la teoría de la información proporciona métodos criptográficos que no pueden descifrarse ni siquiera con una potencia de cálculo ilimitada.
"Un ordenador cuántico a gran escala sería capaz de resolver de manera eficiente problemas NP-completos". La clase de problemas de decisión que puede resolver de manera eficiente (en principio) un ordenador cuántico tolerante a fallos se conoce como BQP. Sin embargo, no se cree que BQP contenga todos los NP y, si no es así, entonces no puede contener ningún problema NP-completo. [15]
Propiedades
Al considerar un problema de decisión como un lenguaje formal en alguna codificación fija, el conjunto NPC de todos los problemas NP-completos no está cerrado bajo:
^ Por ejemplo, simplemente asignar verdadero a cada variable hace que el conjuntivo 18 (y por lo tanto la fórmula completa) sea falso .
^ Cobham, Alan (1965). "La dificultad computacional intrínseca de las funciones". Proc. Lógica, metodología y filosofía de la ciencia II . Holanda Septentrional.
^ J. van Leeuwen (1998). Manual de informática teórica . Elsevier. pág. 84. ISBN.978-0-262-72014-4.
^ J. van Leeuwen (1998). Manual de informática teórica . Elsevier. pág. 80. ISBN.978-0-262-72014-4.
^ Kiersz, Andy. "Un matemático eminente afirma haber resuelto uno de los mayores misterios de las matemáticas, y es uno de los 6 problemas con un premio de un millón de dólares". Business Insider . Consultado el 24 de abril de 2023 .
^ Chen, Jianer; Kanj, Iyad A.; Xia, Ge (6 de septiembre de 2010). "Límites superiores mejorados para la cobertura de vértices". Ciencias de la Computación Teórica . 411 (40): 3736–3756. doi : 10.1016/j.tcs.2010.06.026 . ISSN 0304-3975.
^ Agrawal, M. ; Allender, E.; Rudich, Steven (1998). "Reducciones en la complejidad de circuitos: un teorema de isomorfismo y un teorema de brecha". Revista de Ciencias de la Computación y de Sistemas . 57 (2): 127–143. doi : 10.1006/jcss.1998.1583 . ISSN 1090-2724.
^ Agrawal, M. ; Allender, E.; Impagliazzo, R.; Pitassi, T. ; Rudich, Steven (2001). "Reducción de la complejidad de las reducciones". Computational Complexity . 10 (2): 117–138. doi :10.1007/s00037-001-8191-1. ISSN 1016-3328. S2CID 29017219.
^ Don Knuth , Tracy Larrabee y Paul M. Roberts, Mathematical Writing Archivado el 27 de agosto de 2010 en Wayback Machine , § 25, MAA Notes No. 14 , MAA, 1989 (también Stanford Technical Report, 1987).
^ Ver la encuesta, o [1] Archivado el 7 de junio de 2011 en Wayback Machine .
^ Ball, Philip (2000). "La computadora de ADN ayuda a un viajante de comercio". Nature . doi :10.1038/news000113-10.
^ Berna (1990); Deĭneko, Klinz y Woeginger (2006); Dorn et al. (2005); Lipton y Tarjan (1980).
^ Hemaspaandra, LA; Williams, R. (2012). "Columna 76 de la teoría de la complejidad de las noticias de SIGACT". ACM SIGACT News . 43 (4): 70. doi :10.1145/2421119.2421135. S2CID 13367514.
^ Aaronson, Scott (2010). "BQP y la jerarquía polinomial". En Schulman, Leonard J. (ed.). Actas del 42.º Simposio ACM sobre teoría de la computación, STOC 2010, Cambridge, Massachusetts, EE. UU., 5-8 de junio de 2010. Association for Computing Machinery. págs. 141-150. arXiv : 0910.4698 . doi :10.1145/1806689.1806711. ISBN .978-1-4503-0050-6.
^ Talbot, John; Welsh, DJA (2006), Complejidad y criptografía: una introducción, Cambridge University Press, pág. 57, ISBN9780521617710La cuestión de si NP y co-NP son iguales es probablemente el segundo problema abierto más importante en la teoría de la complejidad, después de la cuestión P versus NP.
Cook, SA (1971). "La complejidad de los procedimientos de demostración de teoremas". Actas del Tercer Simposio Anual de la ACM sobre la Teoría de la Computación, ACM, Nueva York . págs. 151–158. doi : 10.1145/800157.805047 .
Dunne, PE "Una lista comentada de problemas NP-completos seleccionados". COMP202, Departamento de Ciencias de la Computación, Universidad de Liverpool . Consultado el 21 de junio de 2008 .
Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M .; Woeginger, G. "Un compendio de problemas de optimización NP". KTH, Estocolmo . Consultado el 24 de octubre de 2020 .
Dahlke, K. "NP-complete problems". Proyecto de referencia matemática . Consultado el 21 de junio de 2008 .
Karlsson, R. "Lecture 8: NP-complete problems" (PDF) . Departamento de Ciencias de la Computación, Universidad de Lund, Suecia. Archivado desde el original (PDF) el 19 de abril de 2009. Consultado el 21 de junio de 2008 .
Sun, HM "La teoría de la completitud NP". Laboratorio de Seguridad de la Información, Departamento de Ciencias de la Computación, Universidad Nacional Tsing Hua , Ciudad de Hsinchu, Taiwán. Archivado desde el original (PPT) el 2009-09-02 . Consultado el 2008-06-21 .
Jiang, JR "La teoría de la completitud NP" (PPT) . Departamento de Ciencias de la Computación e Ingeniería de la Información, Universidad Nacional Central , Ciudad de Jhongli, Taiwán . Consultado el 21 de junio de 2008 .
Sipser, M. (1997). "Secciones 7.4-7.5 (NP-completitud, problemas NP-completos adicionales)" . Introducción a la teoría de la computación . PWS Publishing. pp. 248-271. ISBN 978-0-534-94728-6.
Papadimitriou, C. (1994). "Capítulo 9 (Problemas NP-completos)". Computational Complexity (1.ª ed.). Addison Wesley. págs. 181–218. ISBN 978-0-201-53082-7.
Complejidad computacional de juegos y rompecabezas
El Tetris es difícil, incluso aproximarse
¡El Buscaminas es NP-completo!
Bern, Marshall (1990). "Algoritmos exactos más rápidos para árboles de Steiner en redes planares". Redes . 20 (1): 109–120. doi :10.1002/net.3230200110..
Deĭneko, Vladimir G.; Klinz, Bettina; Woeginger, Gerhard J. (2006). "Algoritmos exactos para el problema del ciclo hamiltoniano en grafos planares". Operations Research Letters . 34 (3): 269–274. doi :10.1016/j.orl.2005.04.013..
Dorn, Frederic; Penninkx, Eelko; Bodlaender, Hans L .; Fomin, Fedor V. (2005). "Algoritmos exactos eficientes en grafos planares: aprovechamiento de descomposiciones de ramas de corte de esfera". Proc. 13.º Simposio Europeo sobre Algoritmos (ESA '05) . Apuntes de clase en Ciencias de la Computación. Vol. 3669. Springer-Verlag. págs. 95–106. doi :10.1007/11561071_11. ISBN 978-3-540-29118-3..
