NP-integridad

Clase de complejidad

El problema booleano de satisfacibilidad (SAT) pide 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 se puede resolver tan rápido como el SAT, que por tanto es NP-completo.

En la teoría de la complejidad computacional , un problema es NP-completo cuando:

1. Es un problema de decisión , lo que significa que para cualquier entrada al problema, la salida es "sí" o "no".
2. Cuando la respuesta es "sí", esto se puede demostrar mediante la existencia de una solución corta (de longitud polinómica) .
3. La exactitud de cada solución se puede verificar rápidamente (es decir, en tiempo polinómico ) y un algoritmo de búsqueda de fuerza bruta puede encontrar una solución probando todas las soluciones posibles.
4. El problema se puede utilizar para simular cualquier otro problema para el cual podamos verificar rápidamente que una solución es correcta. En este sentido, los problemas NP-completos son los más difíciles de los problemas cuyas soluciones se pueden verificar rápidamente. Si pudiéramos encontrar rápidamente soluciones a algún problema NP completo, podríamos encontrar rápidamente las soluciones de cualquier otro problema cuya solución dada pueda verificarse fácilmente.

El nombre "NP-completo" es la abreviatura de "tiempo polinomial completo 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, cuya validez se puede probar 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-difícil si todo lo que está en NP se puede transformar en tiempo polinómico en él, aunque no esté en NP. Por el contrario, un problema es NP-completo si es tanto NP como NP-difícil. 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 una solución a un problema NP-completo se puede verificar "rápidamente", no se conoce ninguna manera de encontrar una solución rápidamente. Es decir, el tiempo necesario para resolver el problema utilizando cualquier algoritmo actualmente conocido aumenta rápidamente a medida que crece el tamaño del problema. Como consecuencia, determinar si es posible resolver estos problemas rápidamente, llamado problema P versus NP , es uno de los problemas fundamentales no resueltos en la informática actual.

Si bien un método para calcular las soluciones a problemas NP completos sigue sin descubrirse rápidamente, los informáticos y programadores todavía encuentran con frecuencia problemas NP completos. Los problemas NP-completos a menudo se abordan mediante el uso de métodos heurísticos y algoritmos de aproximación .

Descripción general

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 necesaria ]}

No se sabe si todos los problemas en NP se pueden resolver rápidamente; esto se llama problema P versus NP . Pero si cualquier problema NP-completo puede resolverse rápidamente, entonces todos los problemas NP -completos pueden resolverse rápidamente, porque la definición de un problema NP-completo establece que todo problema NP-completo debe ser rápidamente reducible a todo problema NP-completo (es decir, puede resolverse rápidamente). 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 necesaria ]}

Definicion formal

Un problema de decisión es NP-completo si: ^{[ cita necesaria ]} ${\displaystyle \scriptstyle C}$

1. ${\displaystyle \scriptstyle C}$está en NP, y
2. Todo problema en NP es reducible a tiempo polinomial. ^[3] ${\displaystyle \scriptstyle C}$

${\displaystyle \scriptstyle C}$Se puede demostrar que está en NP demostrando que una solución candidata se puede verificar en tiempo polinomial. ${\displaystyle \scriptstyle C}$

Tenga en cuenta que un problema que satisface la condición 2 se dice que es NP-difícil , satisfaga o no la condición 1. ^[4]

Una consecuencia de esta definición es que si tuviéramos un algoritmo de tiempo polinómico (en un UTM , o cualquier otra máquina abstracta equivalente a Turing ) para , podríamos resolver todos los problemas en NP en tiempo polinómico. ${\displaystyle \scriptstyle C}$

Fondo

Diagrama de Euler para conjuntos de problemas P , NP , NP-completo y NP-difícil . 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 es NP-completo).

El concepto de NP-completo se introdujo en 1971 (ver teorema de Cook-Levin ), aunque el término NP-completo se introdujo más tarde. En la conferencia STOC de 1971 , hubo un feroz debate entre los informáticos sobre si los problemas NP-completos podrían resolverse en tiempo polinómico en una máquina determinista de Turing . John Hopcroft llevó a todos los asistentes a la conferencia a un consenso de que la cuestión de si los problemas NP-completos se pueden resolver en tiempo polinomial debería posponerse para resolverse en una fecha posterior, ya que nadie tenía pruebas formales de sus afirmaciones en un sentido u otro. . Esto se conoce como "la cuestión de si P=NP".

Nadie ha podido todavía determinar de manera concluyente si los problemas NP-completos son realmente solucionables en tiempo polinomial, lo que lo convierte en uno de los grandes problemas no resueltos de las matemáticas . El Clay Mathematics Institute ofrece una recompensa de 1 millón de dólares a quien tenga una prueba formal de que P=NP o 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 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 anteriormente se habían demostrado que eran NP-completos; Muchos de estos problemas se recogen en Garey y Johnson (1979).

Problemas NP-completos

Algunos problemas NP-completos, que indican las reducciones que normalmente se utilizan para demostrar su completitud NP

La forma más fácil de demostrar que algún problema nuevo es NP-completo es primero demostrar que está en NP y luego reducirle algún problema NP-completo conocido. Por lo tanto, es útil conocer una variedad de problemas NP-completos. La siguiente lista contiene algunos problemas bien conocidos que son NP-completos cuando se expresan como problemas de decisión.

• Problema de satisfacibilidad booleana (SAT)
• problema de mochila
• Problema del camino hamiltoniano
• Problema del viajante (versión de decisión)
• Problema de isomorfismo de subgrafos
• Problema de suma de subconjuntos
• problema de camarilla
• Problema de cobertura de vértices
• problema de conjunto independiente
• Problema del conjunto dominante
• Problema de coloración de gráficos

A la derecha hay un diagrama de algunos de los problemas y las reducciones que normalmente se utilizan para demostrar su integridad NP. En este diagrama, los problemas se reducen de abajo hacia arriba. Tenga en cuenta que este diagrama es engañoso como descripción de la relación matemática entre estos problemas, ya que existe una reducción de tiempo polinomial entre dos problemas NP-completos cualesquiera; pero indica dónde ha sido más fácil demostrar esta reducción del tiempo polinomial.

A menudo existe sólo una pequeña diferencia entre un problema en P y un problema NP-completo. Por ejemplo, el problema de satisfacibilidad 3 , una restricción del problema de satisfacibilidad booleano, sigue siendo NP-completo, mientras que el problema de satisfacibilidad 2 ligeramente más restringido está en P (específicamente, es NL-completo ), pero el max . 2 sáb. El problema es nuevamente NP-completo. Determinar si un gráfico se puede colorear con 2 colores está en P, pero con 3 colores es NP-completo, incluso cuando se limita a gráficos planos . Determinar si un gráfico es un ciclo o es bipartito es muy fácil (en L ), pero encontrar un subgrafo bipartito máximo o un subgrafo de ciclo máximo es NP-completo. Se puede calcular una solución del problema de la mochila dentro de cualquier porcentaje fijo de la solución óptima en tiempo polinomial, pero encontrar la solución óptima es NP-completo.

Problemas intermedios

Un ejemplo interesante es el problema del isomorfismo gráfico , el problema de la teoría de grafos que consiste en determinar si existe un isomorfismo gráfico entre dos gráficos. Dos grafos son isomórficos si uno puede transformarse en el otro simplemente cambiando el nombre de los vértices . Considere estos dos problemas:

• Isomorfismo del gráfico: ¿Es el gráfico G ₁ isomorfo al gráfico G ₂ ?
• Isomorfismo del subgrafo: ¿Es el gráfico G ₁ isomorfo a un subgrafo del gráfico G ₂ ?

El problema del isomorfismo de subgrafos es NP-completo. Se sospecha que el problema de isomorfismo gráfico no es ni en P ni en NP-completo, aunque sí lo es en NP. Este es un ejemplo de un problema que se considera difícil , pero que no se considera NP completo. Esta clase se llama problemas NP-Intermedios y existe si y sólo si P≠NP.

Resolver problemas NP-completos

En la actualidad, todos los algoritmos conocidos para problemas NP-completos requieren un tiempo superpolinomial en el tamaño de entrada, de hecho exponencial en ${\displaystyle O(n^{k})}$^{[ aclarar ]} para algunos y se desconoce si existen algoritmos más rápidos. ${\displaystyle k>0}$

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 : utilice la aleatoriedad para obtener un tiempo de ejecución promedio más rápido y permita que el algoritmo falle con una pequeña probabilidad. Nota: El método de Monte Carlo no es un ejemplo de algoritmo eficiente en este sentido específico, aunque pueden serlo enfoques evolutivos como los algoritmos genéticos .
• Restricción: Al restringir la estructura de la entrada (por ejemplo, a gráficos planos), 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ístico : Un algoritmo que funciona "razonablemente bien" en muchos casos, pero del cual no hay pruebas de que sea siempre rápido y que siempre produzca un buen resultado. A menudo se utilizan enfoques metaheurísticos .

Un ejemplo de algoritmo heurístico es un algoritmo de coloración codiciosa subóptimo utilizado para colorear gráficos durante la fase de asignación de registros de algunos compiladores, una técnica llamada asignación de registros global de coloración de gráficos. Cada vértice es una variable, los bordes se dibujan entre variables que se utilizan 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. ${\displaystyle O(n\log n)}$

Integridad bajo diferentes tipos de reducción.

En la definición de NP-completo dada anteriormente, el término reducción se usó en el significado técnico de una reducción de muchos uno en tiempo polinomial .

Otro tipo de reducción es la reducción de Turing en tiempo polinomial. Un problema es reducible de Turing en tiempo polinómico a un problema si, dada una subrutina que se resuelve en tiempo polinómico, se puede escribir un programa que llame a esta subrutina y se resuelva en tiempo polinómico. Esto contrasta con la reducibilidad de muchos uno, que tiene la restricción de que el programa sólo puede llamar a la subrutina una vez y el valor de retorno de la subrutina debe ser el valor de retorno del programa. ${\displaystyle \scriptstyle X}$ ${\displaystyle \scriptstyle Y}$ ${\displaystyle \scriptstyle Y}$ ${\displaystyle \scriptstyle X}$

Si se define el análogo de NP-completo con reducciones de Turing en lugar de reducciones de muchos uno, el conjunto de problemas resultante no será menor que NP-completo; es una cuestión abierta si será más grande.

Otro tipo de reducción que también se utiliza a menudo para definir la completitud NP es la reducción muchos uno en el espacio logarítmico , que es una reducción muchos uno que se puede calcular con solo una cantidad logarítmica de espacio. Dado que todos los cálculos que se pueden realizar en el espacio logarítmico también se pueden realizar 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 muchos uno en tiempo polinomial más habituales y nos permite distinguir más clases como P-completa . Aún es un problema abierto si bajo estos tipos de reducciones la definición de cambios NP-completos. Todos los problemas NP-completos conocidos actualmente son NP-completos bajo reducciones de espacio logarítmico. Todos los problemas NP-completos actualmente conocidos siguen siendo NP-completos incluso bajo reducciones mucho más débiles, como reducciones y reducciones. Se sabe que algunos problemas NP-Complete, como SAT, están completos incluso bajo proyecciones de tiempo polilogarítmicas. ^[6] Sin embargo, se sabe que las reducciones AC definen una clase estrictamente más pequeña que las reducciones de tiempo polinomial. ^[7] ${\displaystyle AC_{0}}$ ${\displaystyle NC_{0}}$

Nombrar

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 del libro (de "polinomialmente completo"), de acuerdo con los resultados de una encuesta que había realizado entre la comunidad teórica de informática . ^[8] Otras sugerencias hechas en la encuesta ^[9] incluyeron " hercúleo ", "formidable", "duro" de Steiglitz en honor a Cook, y el acrónimo de Shen Lin "PET", que significa "tiempo probablemente exponencial" . , pero dependiendo de cómo fuera el problema P versus NP , podría significar "tiempo demostrablemente exponencial" o "tiempo previamente exponencial". ^[10]

Conceptos erróneos comunes

Son frecuentes los siguientes conceptos erróneos. ^[11]

• "Los problemas NP-completos son los problemas conocidos más difíciles". Dado que los problemas NP-completos están en NP, su tiempo de ejecución es, como máximo, 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 solucionar, como por ejemplo el problema de la detención .
• "Los problemas NP-completos son difíciles porque hay muchas soluciones diferentes". Por un lado, hay muchos problemas que tienen un espacio de solución igual de grande, pero que pueden resolverse en tiempo polinómico (por ejemplo, árbol de expansión mínima ). Por otro lado, hay problemas NP con como máximo una solución que son NP-difíciles bajo reducción aleatoria de tiempo polinómico (ver Teorema de Valiant-Vazirani ).
• "Resolver problemas NP-completos requiere un tiempo exponencial". Primero, esto implicaría P ≠ NP, lo cual aún es 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 conjuntos independientes y conjuntos dominantes para gráficos planos son NP-completos, pero se pueden resolver en tiempo subexponencial utilizando el teorema del separador plano . ^[12]
• "Cada caso de un problema NP completo es difícil". A menudo, algunos casos, o incluso la mayoría de los casos, pueden ser fáciles de resolver en tiempo polinomial. Sin embargo, a menos que P = NP, cualquier algoritmo de tiempo polinomial debe ser asintóticamente incorrecto en más que polinomialmente muchas de las exponencialmente muchas entradas de un cierto tamaño. ^[13]
• "Si P=NP, todos los cifrados criptográficos se pueden descifrar". Un problema de tiempo polinomial 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 teórica de la información proporciona métodos criptográficos que no se pueden romper ni siquiera con una potencia informática ilimitada.
• "Una computadora cuántica a gran escala podría resolver eficientemente problemas NP completos". La clase de problemas de decisión que pueden resolverse eficientemente (en principio) mediante una computadora cuántica tolerante a fallas se conoce como BQP. Sin embargo, no se cree que BQP contenga todo NP y, si no lo contiene, no puede contener ningún problema de NP completo. ^[14]

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 se cierra en:

• Unión
• intersección
• concatenación
• Estrella Kleene ^{[ ejemplo necesario ]}

No se sabe si NPC está cerrado bajo complementación , ya que NPC= co-NPC si y solo si NP= co-NP , y dado que NP=co-NP es una pregunta abierta . ^[15]

Ver también

• Casi completo
• Gadget (informática)
• teorema de ladner
• Lista de problemas NP completos
• NP-duro
• P = problema NP
• Fuertemente NP-completo
• El viajante (película de 2012)

Referencias

Citas

1. Por ejemplo, simplemente asignar verdadero a cada variable hace que la conjunción 18 (y por lo tanto la fórmula completa) sea falsa . ${\displaystyle {\overline {m}}\lor {\overline {r}}\lor {\overline {s}}}$
2. Cobham, Alan (1965). "La dificultad computacional intrínseca de las funciones". Proc. Lógica, Metodología y Filosofía de la Ciencia II . Holanda del Norte.
3. J. van Leeuwen (1998). Manual de informática teórica . Elsevier. pag. 84.ISBN _ 978-0-262-72014-4.
4. J. van Leeuwen (1998). Manual de informática teórica . Elsevier. pag. 80.ISBN _ 978-0-262-72014-4.
5. Kiersz, Andy. "Un eminente matemático afirma haber resuelto uno de los mayores misterios de las matemáticas, y es uno de los 6 problemas con un premio de 1 millón de dólares". Business Insider . Consultado el 24 de abril de 2023 .
6. Agrawal, M .; Allender, E.; Rüdich, Steven (1998). "Reducciones en la complejidad del circuito: 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.
7. Agrawal, M .; Allender, E.; Impagliazzo, R.; Pitassi, T .; Rudich, Steven (2001). "Reducir la complejidad de las reducciones". Complejidad computacional . 10 (2): 117-138. doi :10.1007/s00037-001-8191-1. ISSN  1016-3328. S2CID  29017219.
8. Don Knuth , Tracy Larrabee y Paul M. Roberts, Escritura matemática Archivado el 27 de agosto de 2010 en Wayback Machine § 25, MAA Notes No. 14 , MAA, 1989 (también Informe técnico de Stanford , 1987).
9. Knuth, DF (1974). "Una propuesta terminológica". Noticias SIGACT . 6 (1): 12-18. doi :10.1145/1811129.1811130. S2CID  45313676.
10. Ver la encuesta, o [1] Archivado el 7 de junio de 2011 en Wayback Machine .
11. Bola, Philip (2000). "La computadora de ADN ayuda al viajante de comercio". Naturaleza . doi :10.1038/noticias000113-10.
12. Berna (1990); Deĭneko, Klinz y Woeginger (2006); Dorn et al. (2005) ; Lipton y Tarjan (1980).Error de harvtxt: sin destino: CITEREFDornPenninksBodlaenderFomin2005 ( ayuda )
13. Hemaspaandra, LA; Williams, R. (2012). "Columna 76 de la teoría de la complejidad de SIGACT News". Noticias ACM SIGACT . 43 (4): 70. doi :10.1145/2421119.2421135. S2CID  13367514.
14. Aaronson, Scott (2010). "BQP y la jerarquía polinómica". En Schulman, Leonard J. (ed.). Actas del 42º Simposio ACM sobre Teoría de la Computación, STOC 2010, Cambridge, Massachusetts, EE. UU., 5 a 8 de junio de 2010 . Asociación para Maquinaria de Computación. págs. 141-150. arXiv : 0910.4698 . doi :10.1145/1806689.1806711.
15. Talbot, Juan; Welsh, DJA (2006), Complejidad y criptografía: una introducción, Cambridge University Press, pág. 57, ISBN 9780521617710La 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.

Fuentes

• Garey, Michael R .; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de la integridad NP . Serie de libros de ciencias matemáticas (1ª ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. SEÑOR  0519066. OCLC  247570676.Este libro es un clásico, desarrolla la teoría y luego cataloga muchos problemas NP-Completos.
• Cook, SA (1971). "La complejidad de los procedimientos de demostración de teoremas". Actas, Tercer Simposio Anual de ACM sobre 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 de NP". KTH, Estocolmo . Consultado el 24 de octubre de 2020 .
• Dahlke, K. "Problemas NP-completos". Proyecto de referencia de matemáticas . Consultado el 21 de junio de 2008 .
• Karlsson, R. "Conferencia 8: Problemas NP-completos" (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 2 de septiembre de 2009 . Consultado el 21 de junio de 2008 .
• 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 .
• Cormen, TH ; Leiserson, CE ; Rivest, RL ; Stein, C. (2001). "Capítulo 34: NP: Integridad". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 966-1021. ISBN 978-0-262-03293-3.
• Sipser, M. (1997). "Secciones 7.4 a 7.5 (completitud de NP, problemas adicionales de NP completo)" . Introducción a la Teoría de la Computación . Publicación PWS. págs. 248–271. ISBN 978-0-534-94728-6.
• Papadimitriou, C. (1994). "Capítulo 9 (problemas NP-completos)". Complejidad computacional (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 aproximado
• ¡El Buscaminas es NP completo!
• Berna, Marshall (1990). "Algoritmos exactos más rápidos para árboles Steiner en redes planas". 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 gráficos planos". Cartas de investigación operativa . 34 (3): 269–274. doi :10.1016/j.orl.2005.04.013..
• Dorn, Federico; Penninkx, Eelko; Bodlaender, Hans L .; Fomin, Fedor V. (2005). "Algoritmos exactos eficientes en gráficos planos: explotación de descomposiciones de ramas cortadas en esferas". Proc. 13º Simposio Europeo sobre Algoritmos (ESA '05) . Apuntes de conferencias sobre informática. vol. 3669. Springer-Verlag. págs. 95-106. doi :10.1007/11561071_11. ISBN 978-3-540-29118-3..
• Lipton, Richard J .; Tarjan, Robert E. (1980). "Aplicaciones del teorema del separador plano". Revista SIAM de Computación . 9 (3): 615–627. doi :10.1137/0209046. S2CID  12961628..

Otras lecturas

• Scott Aaronson , Problemas NP completos y realidad física , ACM SIGACT News, vol. 36, núm. 1 (marzo de 2005), págs.
• Lance Fortnow , El estado del problema P versus NP , Commun. ACM , vol. 52, núm. 9. (2009), págs. 78–86.