Lista de problemas NP-completos

Esta es una lista de algunos de los problemas más conocidos que son NP-completos cuando se expresan como problemas de decisión . Como se conocen miles de problemas de este tipo, esta lista no es en modo alguno exhaustiva. Se pueden encontrar muchos problemas de este tipo en Garey & Johnson (1979).

Gráficos e hipergráficos

Los gráficos aparecen con frecuencia en aplicaciones cotidianas. Algunos ejemplos son las redes biológicas o sociales, que contienen cientos, miles e incluso miles de millones de nodos en algunos casos (por ejemplo, Facebook o LinkedIn ).

1-planaridad ^[1]
Coincidencia tridimensional ^[2]^[3]^{: SP1}
Problema de ancho de banda ^[3]^{: GT40}
Dimensión bipartita ^[3]^{: GT18}
Árbol de expansión mínimo capacitado ^[3]^{: ND5}
Problema de inspección de ruta (también llamado problema del cartero chino ) para grafos mixtos (que tienen aristas dirigidas y no dirigidas). El programa se puede resolver en tiempo polinomial si el grafo tiene todas las aristas dirigidas o no dirigidas. Las variantes incluyen el problema del cartero rural. ^[3]^{: ND25, ND27}
Problema de cobertura de camarilla ^[2]^[3]^{: GT17}
Problema de camarilla ^[2]^[3]^{: GT19}
Coloración completa , también conocida como número acromático ^[3]^{: GT5}
Rango de ciclo
Árbol de expansión con restricciones de grado ^[3]^{: ND1}
Número domático ^[3]^{: GT3}
Conjunto dominante , también conocido como número de dominación ^[3]^{: GT2}

Los casos especiales NP-completos incluyen el problema del conjunto dominante de aristas , es decir, el problema del conjunto dominante en gráficos lineales. Las variantes NP-completas incluyen el problema del conjunto dominante conexo y el problema del árbol de expansión de hojas máximas . ^[3]^{: ND2}

Conjunto de vértices de retroalimentación ^[2]^[3]^{: GT7}
Conjunto de arco de retroalimentación ^[2]^[3]^{: GT8}
Coloración de gráficos ^[2]^[3]^{: GT4}
Problema de homomorfismo de grafos ^[3]^{: GT52}
La partición de un grafo en subgrafos de tipos específicos (triángulos, subgrafos isomorfos , subgrafos hamiltonianos , bosques , emparejamientos perfectos ) se conoce como NP-completo. La partición en grupos es el mismo problema que la coloración del complemento del grafo dado. Un problema relacionado es encontrar una partición que sea óptima en términos del número de aristas entre las partes. ^[3]^{: GT11, GT12, GT13, GT14, GT15, GT16, ND14}
Número de Grundy de un gráfico dirigido. ^[3]^{: GT56}
Completitud hamiltoniana ^[3]^{: GT34}
Problema de trayectoria hamiltoniana , dirigida y no dirigida. ^[2]^[3]^{: GT37, GT38, GT39}
Problema de isomorfismo de subgrafos inducidos
Número de intersección del gráfico ^[3]^{: GT59}
Problema del camino más largo ^[3]^{: ND29}
Subgrafo bipartito máximo o (especialmente con aristas ponderadas) corte máximo . ^[2]^[3]^{: GT25, ND16}
Problema de isomorfismo de máximo subgrafo común ^[3]^{: GT49}
Conjunto independiente máximo ^[3]^{: GT20}
Trayectoria máxima inducida ^[3]^{: GT23}
Conjunto mínimo independiente máximo también conocido como conjunto mínimo independiente dominante ^[4]

Los casos especiales NP-completos incluyen el problema de coincidencia mínima-máxima , ^[3]^{: GT10} , que es esencialmente igual al problema del conjunto que domina los bordes (ver arriba).

Dimensión métrica de un gráfico ^[3]^{: GT61}
Centro k métrico
Árbol de expansión de grado mínimo
Corte k mínimo
Árbol de expansión k mínimo
Prueba menor (verificación de si un gráfico de entrada contiene un gráfico de entrada como menor); lo mismo ocurre con los menores topológicos ${\estilo de visualización G}$ ${\estilo de visualización H}$
Árbol de Steiner , o árbol de expansión mínimo para un subconjunto de los vértices de un gráfico. ^[2] (El árbol de expansión mínimo para un gráfico completo se puede resolver en tiempo polinomial).
Maximización de la modularidad ^[5]
Triángulo monocromático ^[3]^{: GT6}
Ancho de ruta , ^[6] o, equivalentemente, grosor del intervalo y número de separación de vértices ^[7]
Coloración de rangos
k-cartero chino
Árbol de expansión con longitud de ruta total más corta ^[3]^{: ND3}
Prueba de pendiente número dos ^[8]
Reconocimiento de gráficos de cadenas ^[9]
Problema de isomorfismo de subgrafos ^[3]^{: GT48}
Ancho del árbol ^[6]
Probar si un árbol puede representarse como árbol de expansión mínima euclidiana
Cobertura de vértice ^[2]^[3]^{: GT1}

Programación matemática

Problema de 3 particiones ^[3]^{: SP15}
Problema de empaquetamiento de contenedores ^[3]^{: SR1}
El viajante de comercio con cuello de botella ^[3]^{: ND24}
Problema de ubicación de instalaciones no capacitadas
Problema de programación de Flow Shop
Problema de asignación generalizada
Programación entera . La variante en la que se requiere que las variables sean 0 o 1, llamada programación lineal cero-uno, y varias otras variantes también son NP-completas ^[2]^[3]^{: MP1}
Algunos problemas relacionados con la programación de Job-shop
Problema de la mochila , problema de la mochila cuadrático y varias variantes ^[2]^[3]^{: MP9}
Algunos problemas relacionados con la programación de multiprocesadores
Coincidencia numérica tridimensional ^[3]^{: SP16}
Programación de tienda abierta
Problema de partición ^[2]^[3]^{: SP12}
Problema de asignación cuadrática ^[3]^{: ND43}
Programación cuadrática (NP-hard en algunos casos, P si es convexa)
Problema de suma de subconjuntos ^[3]^{: SP13}
Variaciones del problema del viajante de comercio . El problema para grafos es NP-completo si se supone que las longitudes de las aristas son números enteros. El problema para puntos en el plano es NP-completo con la métrica euclidiana discretizada y la métrica rectilínea. Se sabe que el problema es NP-completo con la métrica euclidiana (no discretizada). ^[3]^{: ND22, ND23}

Lenguajes formales y procesamiento de cadenas

Cadena más cercana ^[10]
Problema de subsecuencia común más larga en múltiples secuencias ^[3]^{: SR10}
La variante acotada del problema de correspondencia de Post ^[3]^{: SR11}
Supersecuencia común más corta sobre múltiples secuencias ^[3]^{: SR8}
Extensión del problema de corrección de cuerda a cuerda ^[11]^[3]^{: SR8}

Juegos y rompecabezas

Bolsa (Corral) ^[12]
Acorazado
Toros y vacas , comercializado como Master Mind : ciertos problemas de optimización, pero no el juego en sí.
Rompecabezas de combinación de bordes
Fillomino ^[13]
( Generalizado ) Carta blanca ^[14]
Goishi Hiroi
Hashiwokakero ^[15]
Hola despierto ^[16]
( Generalizada ) Locura instantánea ^[3]^{: GP15}
Kakuro (Sumas cruzadas) ^[17]
Reino Unido ^[18]
Kuromasu (también conocido como Kurodoko) ^[19]
Tanque láser ^[20]
Lemmings (con un límite de tiempo polinomial) ^[21]
Iluminar ^[22]
Solitario Mahjong (mirando las fichas debajo)
Masyu ^[23]
Problema de consistencia del buscaminas ^[24] (pero ver Scott, Stege y van Rooij ^[25] )
Nonogramas
Enlace numérico
Nurikabe ^[26]
Pandemia ( generalizada ) ^[27]
Solitario de clavijas
Finalización de n-Queens
Solución óptima para el cubo de Rubik $N \times N \times N$ ^[28]
Mismo juego
Shaka-shaka
Slither Link en una variedad de cuadrículas ^[29]^[30]^[31]
Sudoku ( generalizado ) ^[29]^[32]
Tatamibari
Espectáculo de Tentai
Problemas relacionados con el Tetris ^[33]
Aritmética verbal

Otro

Problema de asignación de amarres ^[34]
Intermediación
Ensamblando un bloque óptimo de Bitcoin . ^[35]
Problema de satisfacibilidad booleano (SAT). ^[2]^[3]^{: LO1} Existen muchas variantes que también son NP-completas. Una variante importante es aquella en la que cada cláusula tiene exactamente tres literales (3SAT), ya que se utiliza en la prueba de muchos otros resultados de NP-completitud. ^[3]^{: p. 48}
Problema de satisfacibilidad de circuitos
Consulta booleana conjuntiva ^[3]^{: SR31}
Ordenamiento cíclico ^[36]
Problema de cobertura exacta . Sigue siendo NP-completo para conjuntos de 3. Resoluble en tiempo polinomial para conjuntos de 2 (esta es una coincidencia ). ^[2]^[3]^{: SP2}
Encontrar la solución mínima global de un problema de Hartree-Fock ^[37]
Prueba de planaridad ascendente ^[8]
Problemas entre hospitales y residentes con las parejas
Género de nudos ^[38]
Completar un cuadrado latino (el problema de determinar si un cuadrado parcialmente lleno puede completarse)
Máxima 2-satisfacibilidad ^[3]^{: LO5}
Submatriz de volumen máximo : problema de selección del subconjunto mejor condicionado de una matriz más grande. Esta clase de problema está asociada con factorizaciones QR que revelan rangos y diseño experimental óptimo D. ^[39] $m\veces n$
Cadenas de adición mínimas para secuencias. ^[40] Se desconoce la complejidad de las cadenas de adición mínimas para números individuales. ^[41]
Lógica modal S5 - Satisfacción
Problema de distancia de clasificación de panqueques para cadenas ^[42]
Solubilidad de polinomios cuadráticos de dos variables sobre los números enteros. ^[43] Dados números enteros positivos , decidir la existencia de números enteros positivos tales que $\textstyle A,B,C$ ${\estilo de visualización x,y}$ $Ax^{2}+By-C=0$
En el mismo artículo ^[43] se afirma la existencia de raíces cuadradas modulares acotadas con módulo compuesto arbitrario. Dados números enteros positivos , se decide la existencia de un número entero tal que . El problema sigue siendo NP-completo incluso si se proporciona una factorización prima de . $\textstyle A,B,C\geq 0$ $x\en [0,C]$ $x^{2}\equiv A{\bmod {B}}$ ${\estilo de visualización B}$
Serialización de historiales de bases de datos ^[3]^{: SR33}
Cobertura de conjuntos (también llamada problema de "cobertura mínima"). Es equivalente, mediante la transposición de la matriz de incidencia, al problema del conjunto de impacto. ^[2]^[3]^{: SP5, SP8}
Conjunto de embalaje ^[2]^[3]^{: SP3}
Problema de división de conjuntos ^[3]^{: SP4}
Programación para minimizar el tiempo de finalización ponderado
Ordenación por bloques ^[44] (Ordenación por movimientos de bloques)
Aproximación dispersa
Variaciones del problema del árbol de Steiner . Específicamente, con la métrica euclidiana discretizada, la métrica rectilínea. Se sabe que el problema es NP-hard con la métrica euclidiana (no discretizada). ^[3]^{: ND13}
Modelo de Ising tridimensional ^[45]

Véase también

Notas

^ Grigoriev y Bodlaender (2007).
^ abcdefghijklmnopq Karp (1972)
^ abcdefghijklmnopqrstu vwxyz aa ab ac ad ae af ag ah ai aj ak al am an ao ap aq ar as at au av aw ax ay az ba bb bc bd be Garey & Johnson (1979)
^ Conjunto dominante independiente mínimo
^ Brandes, Ulrik ; Delling, Daniel; Gaertler, Marco; Görke, Robert; Hoefer, Martin; Nikoloski, Zoran; Wagner, Dorothea (2006), Maximizar la modularidad es difícil , arXiv : physics/0608255 , Bibcode :2006physics...8255B
^ por Arnborg, Corneil y Proskurowski (1987)
^ Kashiwabara y Fujisawa (1979); Ohtsuki et al. (1979); Lengauer (1981).
^ ab Garg, Ashim; Tamassia, Roberto (1995). "Sobre la complejidad computacional de las pruebas de planaridad ascendente y rectilínea". Lecture Notes in Computer Science . Vol. 894/1995. págs. 286– 297. doi :10.1007/3-540-58950-3_384. ISBN 978-3-540-58950-1.
^ Schaefer, Marcus; Sedgwick, Eric; Štefankovič, Daniel (septiembre de 2003). "Reconocimiento de grafos de cadenas en NP". Journal of Computer and System Sciences . 67 (2): 365– 380. doi : 10.1016/S0022-0000(03)00045-X .
^ Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003), "Distinguir problemas de selección de cadenas", Información y computación , 185 (1): 41– 55, doi : 10.1016/S0890-5401(03)00057-9 , MR 1994748
^ Wagner, Robert A. (mayo de 1975). "Sobre la complejidad del problema de corrección de cadena a cadena extendido". Actas del séptimo simposio anual de la ACM sobre teoría de la computación - STOC '75 . págs. 218-223 . doi :10.1145/800116.803771. ISBN 9781450374194. Número de identificación del sujeto 18705107.
^ Friedman, Erich. "Los rompecabezas de corral son NP-completos" (PDF) . Consultado el 17 de agosto de 2021 .
^ Yato, Takauki (2003). Complejidad y completitud de la búsqueda de otra solución y su aplicación a los rompecabezas . CiteSeerX 10.1.1.103.8380 .
^ Malte Helmert, Resultados de complejidad para dominios de referencia estándar en planificación, Inteligencia Artificial 143(2):219-262, 2003.
^ "HASHIWOKAKERO es NP-completo".
^ Holzer y Ruepp (2007)
^ Takahiro, Seta (5 de febrero de 2002). "Las complejidades de los acertijos, problemas de suma cruzada y otras soluciones (ASP)" (PDF) . Consultado el 18 de noviembre de 2018 .
^ Nguyen, Viet-Ha; Perrot, Kévin; Vallet, Mathieu (24 de junio de 2020). "NP-completitud del juego KingdominoTM". Ciencias Informáticas Teóricas . 822 : 23– 35. doi : 10.1016/j.tcs.2020.04.007 . ISSN 0304-3975. S2CID 218552723.
^ Kölker, Jonas (2012). "Kurodoko es NP-completo" (PDF) . Journal of Information Processing . 20 (3): 694– 706. doi :10.2197/ipsjjip.20.694. S2CID 46486962. Archivado desde el original (PDF) el 12 de febrero de 2020.
^ Alexandersson, Per; Restadh, Petter (2020). "LaserTank es NP-completo". Aspectos matemáticos de las ciencias de la computación y la información . Apuntes de clase en informática. Vol. 11989. Springer International Publishing. págs. 333– 338. arXiv : 1908.05966 . doi :10.1007/978-3-030-43120-4_26. ISBN . 978-3-030-43119-8.S2CID201058355 .
^ Cormode, Graham (2004). La dificultad del juego de los lemmings, o Oh no, más pruebas de NP-completitud (PDF) .
^ Light Up es NP-Completo
^ Friedman, Erich (27 de marzo de 2012). «Los rompecabezas de perlas son NP-completos». Archivado desde el original el 4 de febrero de 2012.
^ Kaye (2000)
^ Allan Scott, Ulrike Stege, Iris van Rooij, Minesweeper puede no ser NP-completo, pero aun así es difícil, The Mathematical Intelligencer 33 :4 (2011), págs. 5-17.
^ Holzer, Markus; Klein, Andreas; Kutrib, Martin; Ruepp, Oliver (2011). "Complejidad computacional de NURIKABE". Fundamenta Informaticae . 110 ( 1– 4): 159– 174. doi :10.3233/FI-2011-534.
^ Nakai, Kenichiro; Takenaga, Yasuhiko (2012). "NP-Integridad de la pandemia". Revista de Procesamiento de Información . 20 (3): 723– 726. doi : 10.2197/ipsjjip.20.723 . ISSN 1882-6652.
^ Demaine, Erik; Eisenstat, Sarah; Rudoy, Mikhail (2018). Resolver el cubo de Rubik de manera óptima es NP-completo . 35.° Simposio sobre aspectos teóricos de la informática (STACS 2018). doi : 10.4230/LIPIcs.STACS.2018.24 .
^ ab Sato, Takayuki; Seta, Takahiro (1987). Complejidad y completitud de la búsqueda de otra solución y su aplicación a los rompecabezas (PDF) . Simposio internacional sobre algoritmos (SIGAL 1987).
^ Nukui; Uejima (marzo de 2007). "Completitud ASP del rompecabezas Slither Link en varias cuadrículas". Ipsj Sig Notes . 2007 (23): 129– 136.
^ Kölker, Jonas (2012). "Variantes seleccionadas de Slither Link son NP-completas". Revista de procesamiento de la información . 20 (3): 709– 712. doi : 10.2197/ipsjjip.20.709 .
^ UNA ENCUESTA SOBRE ROMPECABEZAS NP-COMPLETAS, Sección 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; marzo de 2008. (icga2008.pdf)
^ Demaine, Eric D.; Hohenberger, Susan; Liben-Nowell, David (25–28 de julio de 2003). Tetris es difícil, incluso para aproximarse (PDF) . Actas de la 9.ª Conferencia Internacional de Informática y Combinatoria (COCOON 2003). Big Sky, Montana.
^ Lim, Andrew (1998), "El problema de la planificación de los atracaderos", Operations Research Letters , 22 ( 2–3 ): 105–110 , doi :10.1016/S0167-6377(98)00010-8, MR 1653377
^ J. Bonneau, "La minería de bitcoins es NP-hard"
^ Galil, Zvi; Megiddo, Nimrod (octubre de 1977). "El ordenamiento cíclico es NP-completo". Theoretical Computer Science . 5 (2): 179– 182. doi : 10.1016/0304-3975(77)90005-6 .
^ Whitfield, James Daniel; Love, Peter John; Aspuru-Guzik, Alán (2013). "Complejidad computacional en la estructura electrónica". Phys. Chem. Chem. Phys . 15 (2): 397– 411. arXiv : 1208.3334 . Bibcode :2013PCCP...15..397W. doi :10.1039/C2CP42695A. PMID 23172634. S2CID 12351374.
^ Agol, Ian ; Hass, Joel ; Thurston, William (19 de mayo de 2002). "El género de nudos de 3 variedades es NP-completo". Actas del trigésimo cuarto simposio anual de la ACM sobre teoría de la computación . STOC '02. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 761– 766. arXiv : math/0205057 . doi :10.1145/509907.510016. ISBN 978-1-58113-495-7.S2CID10401375 .
^ Çivril, Ali; Magdon-Ismail, Malik (2009), "Sobre la selección de una submatriz de volumen máximo de una matriz y problemas relacionados" (PDF) , Theoretical Computer Science , 410 ( 47– 49): 4801– 4811, doi :10.1016/j.tcs.2009.06.018, MR 2583677, archivado desde el original (PDF) el 3 de febrero de 2015
^ Peter Downey, Benton Leong y Ravi Sethi. "Cálculo de secuencias con cadenas de adición", SIAM J. Comput., 10(3), 638–646, 1981
^ DJ Bernstein, "Algoritmo de exponenciación de Pippinger" (borrador)
^ Hurkens, C.; Iersel, LV; Keijsper, J.; Kelk, S.; Stougie, L.; Tromp, J. (2007). "Inversiones de prefijos en cadenas binarias y ternarias". SIAM J. Discrete Math . 21 (3): 592– 611. arXiv : math/0602456 . doi :10.1137/060664252.
^ ab Manders, Kenneth; Adleman, Leonard (1976). "Problemas de decisión NP-completos para polinomios cuadráticos". Actas del octavo simposio anual de la ACM sobre teoría de la computación - STOC '76 . págs. 23– 29. doi :10.1145/800113.803627. ISBN 9781450374149. Número de identificación del sujeto 18885088.
^ Bein, WW; Larmore, LL; Latifi, S.; Sudborough, IH (1 de enero de 2002). "La ordenación por bloques es difícil". Actas del Simposio internacional sobre arquitecturas paralelas, algoritmos y redes. I-SPAN'02 . págs. 307– 312. doi :10.1109/ISPAN.2002.1004305. ISBN 978-0-7695-1579-3. Número de identificación del sujeto 32222403.
^ Barry Arthur Cipra , "El modelo de Ising es NP-completo", SIAM News, vol. 33, n.º 6.

Referencias

General

Garey, Michael R. ; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . Serie de libros sobre ciencias matemáticas (1.ª ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. Sr. 0519066. OCLC 247570676.Este libro es un clásico que 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 del Tercer Simposio Anual de la ACM sobre la Teoría de la Computación, ACM, Nueva York . pp. 151– 158. doi : 10.1145/800157.805047 .
Karp, Richard M. (1972). "Reducibilidad entre problemas combinatorios". En Miller, Raymond E.; Thatcher, James W. (eds.). Complejidad de los cálculos informáticos . Plenum. págs. 85– 103.
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 NADA, Estocolmo . Consultado el 21 de junio de 2008 .
Dahlke, K. "NP-complete problems". Proyecto de referencia matemática . Consultado el 21 de junio de 2008 .

Problemas específicos

Friedman, E (2002). "Los rompecabezas de perlas son NP-completos". Stetson University, DeLand, Florida. Archivado desde el original el 4 de septiembre de 2006. Consultado el 21 de junio de 2008 .
Grigoriev, A; Bodlaender, HL (2007). "Algoritmos para grafos integrables con pocos cruces por arista". Algorithmica . 49 (1): 1– 11. CiteSeerX 10.1.1.61.3576 . doi :10.1007/s00453-007-0010-x. MR 2344391. S2CID 8174422.
Hartung, S; Nichterlein, A (2012). "NP-dureza y manejabilidad de parámetros fijos de la realización de secuencias de grados con grafos acíclicos dirigidos". How the World Computes . Apuntes de clase en informática. Vol. 7318. Springer, Berlín, Heidelberg. págs. 283– 292. CiteSeerX 10.1.1.377.2077 . doi :10.1007/978-3-642-30870-3_29. ISBN 978-3-642-30869-7.S2CID6112925 .
Holzer, Markus; Ruepp, Oliver (2007). "Los problemas del diseño de interiores: un análisis de la complejidad del juego Heyawake" (PDF) . Actas de la 4.ª Conferencia internacional sobre diversión con algoritmos, LNCS 4475. Springer, Berlín/Heidelberg. pp. 198– 212. doi :10.1007/978-3-540-72914-3_18. ISBN . 978-3-540-72913-6.
Kaye, Richard (2000). "El Buscaminas es NP-completo". Mathematical Intelligencer . 22 (2): 9– 15. doi :10.1007/BF03025367. S2CID 122435790.Más información disponible en línea en las páginas de Buscaminas de Richard Kaye.
Kashiwabara, T.; Fujisawa, T. (1979). "NP-completitud del problema de encontrar un grafo de intervalo de número mínimo de clique que contenga un grafo dado como subgrafo". Actas . Simposio Internacional sobre Circuitos y Sistemas . págs. 657– 660.
Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979). "Asignación de puertas lógicas unidimensionales y gráficos de intervalos". IEEE Transactions on Circuits and Systems . 26 (9): 675– 684. doi :10.1109/TCS.1979.1084695.
Lengauer, Thomas (1981). "Guijarros blancos y negros y separación de grafos". Acta Informatica . 16 (4): 465– 475. doi :10.1007/BF00264496. S2CID 19415148.
Arnborg, Stefan; Corneil, Derek G .; Proskurowski, Andrzej (1987). "Complejidad de encontrar incrustaciones en un árbol k ". Revista SIAM sobre métodos algebraicos y discretos . 8 (2): 277– 284. doi :10.1137/0608024.
Cormode, Graham (2004). "La dificultad del juego de los lemmings, o Oh no, más pruebas de NP-completitud". Actas de la Tercera Conferencia Internacional sobre Diversión con Algoritmos (FUN 2004) . pp. 65– 76.

Enlaces externos

Un compendio de problemas de optimización NP
Gráfica de problemas NP-completos

[FOOTNOTEGrigorievBodlaender2007-1] Grigoriev y Bodlaender (2007).

[karp-2] q Karp (1972)

[gj1979-3] qrstu vwxyz aa ab ac ad ae af ag ah ai aj ak al am an ao ap aq ar as at au av aw ax ay az ba bb bc bd be Garey & Johnson (1979)

[4] Conjunto dominante independiente mínimo

[5] Brandes, Ulrik ; Delling, Daniel; Gaertler, Marco; Görke, Robert; Hoefer, Martin; Nikoloski, Zoran; Wagner, Dorothea (2006), Maximizar la modularidad es difícil , arXiv : physics/0608255 , Bibcode :2006physics...8255B

[acp1987-6] r Arnborg, Corneil y Proskurowski (1987)

[7] Kashiwabara y Fujisawa (1979); Ohtsuki et al. (1979); Lengauer (1981).

[Comp2Planar-8] Garg, Ashim; Tamassia, Roberto (1995). "Sobre la complejidad computacional de las pruebas de planaridad ascendente y rectilínea". Lecture Notes in Computer Science . Vol. 894/1995. págs. 286– 297. doi :10.1007/3-540-58950-3_384. ISBN 978-3-540-58950-1.

[9] Schaefer, Marcus; Sedgwick, Eric; Štefankovič, Daniel (septiembre de 2003). "Reconocimiento de grafos de cadenas en NP". Journal of Computer and System Sciences . 67 (2): 365– 380. doi : 10.1016/S0022-0000(03)00045-X .

[10] Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003), "Distinguir problemas de selección de cadenas", Información y computación , 185 (1): 41– 55, doi : 10.1016/S0890-5401(03)00057-9 , MR 1994748

[11] Wagner, Robert A. (mayo de 1975). "Sobre la complejidad del problema de corrección de cadena a cadena extendido". Actas del séptimo simposio anual de la ACM sobre teoría de la computación - STOC '75 . págs. 218-223 . doi :10.1145/800116.803771. ISBN 9781450374194. Número de identificación del sujeto 18705107.

[12] Friedman, Erich. "Los rompecabezas de corral son NP-completos" (PDF) . Consultado el 17 de agosto de 2021 .

[13] Yato, Takauki (2003). Complejidad y completitud de la búsqueda de otra solución y su aplicación a los rompecabezas . CiteSeerX 10.1.1.103.8380 .

[14] Malte Helmert, Resultados de complejidad para dominios de referencia estándar en planificación, Inteligencia Artificial 143(2):219-262, 2003.

[15] "HASHIWOKAKERO es NP-completo".

[Holzer-Ruepp07-16] Holzer y Ruepp (2007)

[17] Takahiro, Seta (5 de febrero de 2002). "Las complejidades de los acertijos, problemas de suma cruzada y otras soluciones (ASP)" (PDF) . Consultado el 18 de noviembre de 2018 .

[18] Nguyen, Viet-Ha; Perrot, Kévin; Vallet, Mathieu (24 de junio de 2020). "NP-completitud del juego KingdominoTM". Ciencias Informáticas Teóricas . 822 : 23– 35. doi : 10.1016/j.tcs.2020.04.007 . ISSN 0304-3975. S2CID 218552723.

[Kölker12b-19] Kölker, Jonas (2012). "Kurodoko es NP-completo" (PDF) . Journal of Information Processing . 20 (3): 694– 706. doi :10.2197/ipsjjip.20.694. S2CID 46486962. Archivado desde el original (PDF) el 12 de febrero de 2020.

[20] Alexandersson, Per; Restadh, Petter (2020). "LaserTank es NP-completo". Aspectos matemáticos de las ciencias de la computación y la información . Apuntes de clase en informática. Vol. 11989. Springer International Publishing. págs. 333– 338. arXiv : 1908.05966 . doi :10.1007/978-3-030-43120-4_26. ISBN . 978-3-030-43119-8.S2CID201058355 .

[Cormode04-21] Cormode, Graham (2004). La dificultad del juego de los lemmings, o Oh no, más pruebas de NP-completitud (PDF) .

[22] Light Up es NP-Completo

[Friedman-23] Friedman, Erich (27 de marzo de 2012). «Los rompecabezas de perlas son NP-completos». Archivado desde el original el 4 de febrero de 2012.

[24] Kaye (2000)

[25] Allan Scott, Ulrike Stege, Iris van Rooij, Minesweeper puede no ser NP-completo, pero aun así es difícil, The Mathematical Intelligencer 33 :4 (2011), págs. 5-17.

[26] Holzer, Markus; Klein, Andreas; Kutrib, Martin; Ruepp, Oliver (2011). "Complejidad computacional de NURIKABE". Fundamenta Informaticae . 110 ( 1– 4): 159– 174. doi :10.3233/FI-2011-534.

[27] Nakai, Kenichiro; Takenaga, Yasuhiko (2012). "NP-Integridad de la pandemia". Revista de Procesamiento de Información . 20 (3): 723– 726. doi : 10.2197/ipsjjip.20.723 . ISSN 1882-6652.

[28] Demaine, Erik; Eisenstat, Sarah; Rudoy, Mikhail (2018). Resolver el cubo de Rubik de manera óptima es NP-completo . 35.° Simposio sobre aspectos teóricos de la informática (STACS 2018). doi : 10.4230/LIPIcs.STACS.2018.24 .

[sigal87-29] Sato, Takayuki; Seta, Takahiro (1987). Complejidad y completitud de la búsqueda de otra solución y su aplicación a los rompecabezas (PDF) . Simposio internacional sobre algoritmos (SIGAL 1987).

[NU07-30] Nukui; Uejima (marzo de 2007). "Completitud ASP del rompecabezas Slither Link en varias cuadrículas". Ipsj Sig Notes . 2007 (23): 129– 136.

[Kölker12c-31] Kölker, Jonas (2012). "Variantes seleccionadas de Slither Link son NP-completas". Revista de procesamiento de la información . 20 (3): 709– 712. doi : 10.2197/ipsjjip.20.709 .

[32] UNA ENCUESTA SOBRE ROMPECABEZAS NP-COMPLETAS, Sección 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; marzo de 2008. (icga2008.pdf)

[33] Demaine, Eric D.; Hohenberger, Susan; Liben-Nowell, David (25–28 de julio de 2003). Tetris es difícil, incluso para aproximarse (PDF) . Actas de la 9.ª Conferencia Internacional de Informática y Combinatoria (COCOON 2003). Big Sky, Montana.

[34] Lim, Andrew (1998), "El problema de la planificación de los atracaderos", Operations Research Letters , 22 ( 2–3 ): 105–110 , doi :10.1016/S0167-6377(98)00010-8, MR 1653377

[35] J. Bonneau, "La minería de bitcoins es NP-hard"

[36] Galil, Zvi; Megiddo, Nimrod (octubre de 1977). "El ordenamiento cíclico es NP-completo". Theoretical Computer Science . 5 (2): 179– 182. doi : 10.1016/0304-3975(77)90005-6 .

[37] Whitfield, James Daniel; Love, Peter John; Aspuru-Guzik, Alán (2013). "Complejidad computacional en la estructura electrónica". Phys. Chem. Chem. Phys . 15 (2): 397– 411. arXiv : 1208.3334 . Bibcode :2013PCCP...15..397W. doi :10.1039/C2CP42695A. PMID 23172634. S2CID 12351374.

[38] Agol, Ian ; Hass, Joel ; Thurston, William (19 de mayo de 2002). "El género de nudos de 3 variedades es NP-completo". Actas del trigésimo cuarto simposio anual de la ACM sobre teoría de la computación . STOC '02. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 761– 766. arXiv : math/0205057 . doi :10.1145/509907.510016. ISBN 978-1-58113-495-7.S2CID10401375 .

[39] Çivril, Ali; Magdon-Ismail, Malik (2009), "Sobre la selección de una submatriz de volumen máximo de una matriz y problemas relacionados" (PDF) , Theoretical Computer Science , 410 ( 47– 49): 4801– 4811, doi :10.1016/j.tcs.2009.06.018, MR 2583677, archivado desde el original (PDF) el 3 de febrero de 2015

[40] Peter Downey, Benton Leong y Ravi Sethi. "Cálculo de secuencias con cadenas de adición", SIAM J. Comput., 10(3), 638–646, 1981

[41] DJ Bernstein, "Algoritmo de exponenciación de Pippinger" (borrador)

[42] Hurkens, C.; Iersel, LV; Keijsper, J.; Kelk, S.; Stougie, L.; Tromp, J. (2007). "Inversiones de prefijos en cadenas binarias y ternarias". SIAM J. Discrete Math . 21 (3): 592– 611. arXiv : math/0602456 . doi :10.1137/060664252.

[NP-complete_decision_problems_for_Quadratic_Polynomials-43] Manders, Kenneth; Adleman, Leonard (1976). "Problemas de decisión NP-completos para polinomios cuadráticos". Actas del octavo simposio anual de la ACM sobre teoría de la computación - STOC '76 . págs. 23– 29. doi :10.1145/800113.803627. ISBN 9781450374149. Número de identificación del sujeto 18885088.

[44] Bein, WW; Larmore, LL; Latifi, S.; Sudborough, IH (1 de enero de 2002). "La ordenación por bloques es difícil". Actas del Simposio internacional sobre arquitecturas paralelas, algoritmos y redes. I-SPAN'02 . págs. 307– 312. doi :10.1109/ISPAN.2002.1004305. ISBN 978-0-7695-1579-3. Número de identificación del sujeto 32222403.

[45] Barry Arthur Cipra , "El modelo de Ising es NP-completo", SIAM News, vol. 33, n.º 6.