Lista de problemas NP completos

Esta es una lista de algunos de los problemas más comúnmente conocidos que son NP-completos cuando se expresan como problemas de decisión . Como se conocen cientos de problemas de este tipo, esta lista no es de ninguna manera exhaustiva. Muchos problemas de este tipo se pueden encontrar en Garey y Johnson (1979).

Gráficos e hipergrafías.

Los gráficos aparecen con frecuencia en aplicaciones cotidianas. Los ejemplos incluyen redes biológicas o sociales, que en algunos casos contienen cientos, miles e incluso miles de millones de nodos (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 gráficos mixtos (que tienen bordes dirigidos y no dirigidos). El programa se puede resolver en tiempo polinómico si el gráfico 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 conocido como número acromático ^[3]^{: GT5}
Rango de ciclo
Árbol de expansión de grados restringidos ^[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 conectado y el problema del árbol de máxima extensión de hojas . ^[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 gráfico ^[3]^{: GT52}
La partición de gráficos en subgrafos de tipos específicos (triángulos, subgrafos isomórficos , subgrafos hamiltonianos , bosques , coincidencias perfectas ) se conocen como NP-completos. La partición en camarillas es el mismo problema que colorear el complemento del gráfico 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 grafo dirigido. ^[3]^{: GT56}
Finalización hamiltoniana ^[3]^{: GT34}
Problema de caminos hamiltonianos , dirigidos y no dirigidos. ^[2]^[3]^{: GT37, GT38, GT39}
Problema de isomorfismo de subgrafo inducido
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 bordes ponderados) corte máximo . ^[2]^[3]^{: GT25, ND16}
Problema de isomorfismo de subgrafo común máximo ^[3]^{: GT49}
Conjunto independiente máximo ^[3]^{: GT20}
Ruta inducida máxima ^[3]^{: GT23}
Conjunto independiente mínimo máximo también conocido como conjunto dominante mínimo independiente ^[4]

Los casos especiales de NP-completo incluyen el problema de coincidencia mínimo-máximo , ^[3]^{: GT10} , que es esencialmente igual al problema del conjunto dominante de bordes (ver arriba).

Dimensión métrica de un gráfico ^[3]^{: GT61}
Centro k métrico
Árbol de extensión de grados mínimos
Corte k mínimo
Árbol de expansión k mínimo
Pruebas menores (verificar si un gráfico de entrada contiene un gráfico de entrada como menor); lo mismo ocurre con los menores topológicos $G$ $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 polinómico).
Maximización de la modularidad ^[5]
Triángulo monocromático ^[3]^{: GT6}
Ancho de ruta , ^[6] o, equivalentemente, espesor de intervalo y número de separación de vértices ^[7]
Coloración de rango
k-cartero chino
Árbol de extensión de longitud de ruta total más corta ^[3]^{: ND3}
Prueba de pendiente número dos ^[8]
Reconocer gráficos de cadenas ^[9]
Problema de isomorfismo de subgrafos ^[3]^{: GT48}
Ancho del árbol ^[6]
Probar si un árbol puede representarse como un árbol de expansión mínima euclidiana
Cubierta de vértice ^[2]^[3]^{: GT1}

programación matemática

Problema de 3 particiones ^[3]^{: SP15}
Problema de embalaje del contenedor ^[3]^{: SR1}
Vendedor ambulante cuello de botella ^[3]^{: ND24}
Problema de ubicación de instalaciones no capacitadas
Problema de programación del taller de flujo
Problema de asignación generalizada
Programación entera . La variante donde se requiere que las variables sean 0 o 1, llamada programación lineal cero-uno, y varias otras variantes también son NP-completa ^[2]^[3]^{: MP1}
Algunos problemas relacionados con la programación del taller de trabajo
Problema de mochila , problema de mochila cuadrático y varias variantes ^[2]^[3]^{: MP9}
Algunos problemas relacionados con la programación multiprocesador
Coincidencia numérica tridimensional ^[3]^{: SP16}
Programación de tiendas abiertas
Problema de partición ^[2]^[3]^{: SP12}
Problema de asignación cuadrática ^[3]^{: ND43}
Programación cuadrática (NP-dura en algunos casos, P si es convexa)
Problema de suma de subconjuntos ^[3]^{: SP13}
Variaciones sobre el problema del viajante de comercio . El problema de los gráficos es NP-completo si las longitudes de los bordes se suponen enteras. 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-difícil con la métrica euclidiana (no discretizada). ^[3]^{: ND22, ND23}
Problema de ruta de vehículos

Lenguajes formales y procesamiento de cadenas.

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

Juegos y rompecabezas

Bolsa (Corral) ^[12]
Acorazado
Bulls and Cows , comercializado como Master Mind : ciertos problemas de optimización pero no el juego en sí.
Rompecabezas de combinación de bordes
Fillominó ^[13]
( Generalizado ) FreeCell ^[14]
Hiroi Goishi
Hashiwokakero ^[15]
Hola, despierta ^[16]
( Generalizado ) Locura instantánea ^[3]^{: GP15}
Kakuro (sumas cruzadas) ^[17]
Reinoino ^[18]
Kuromasu (también conocido como Kurodoko) ^[19]
Tanque láser ^[20]
Lemmings (con un límite de tiempo polinómico) ^[21]
Iluminar ^[22]
Solitario Mahjong (con mirar debajo de las fichas)
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 clavija
Finalización de n-reinas
Solución óptima para el cubo de Rubik $N \times N \times N$ ^[28]
Mismo juego
( Generalizado ) Conjunto ^[29]
Shakashaka
Slither Link en una variedad de cuadrículas ^[30]^[31]^[32]
Cubo de serpiente ^[33]
( Generalizado ) Sudoku ^[30]^[34]
Tatamibari
Espectáculo tentai
Problemas relacionados con el Tetris ^[35]
Aritmética verbal

Otro

Problema de asignación de atraques ^[36]
intermediación
Armado de un bloque Bitcoin óptimo . ^[37]
Problema booleano de satisfacibilidad (SAT). ^[2]^[3]^{: LO1} Hay muchas variaciones que también son NP-completas. Una variante importante es cuando cada cláusula tiene exactamente tres literales (3SAT), ya que se utiliza en la prueba de muchos otros resultados de completitud NP. ^[3]^{: pág. 48}
Problema de satisfacibilidad del circuito
Consulta booleana conjuntiva ^[3]^{: SR31}
Ordenamiento cíclico ^[38]
Problema de cobertura exacto . Sigue siendo NP completo durante 3 series. Resoluble en tiempo polinomial para 2 conjuntos (esta es una coincidencia ). ^[2]^[3]^{: SP2}
Encontrar la solución mínima global de un problema de Hartree-Fock ^[39]
Prueba de planaridad ascendente ^[8]
Problema de hospitales y residentes con las parejas
Género de nudos ^[40]
Completar un cuadrado latino (el problema de determinar si se puede completar un cuadrado parcialmente lleno)
Máxima 2-satisfacibilidad ^[3]^{: LO5}
Submatriz de volumen máximo : problema de seleccionar el subconjunto mejor acondicionado de una matriz más grande. Esta clase de problema está asociada con factorizaciones QR reveladoras de rango y diseño experimental óptimo D. ^[41] $m\veces n$
Cadenas de adición mínima para secuencias. ^[42] Se desconoce la complejidad de las cadenas de suma mínima para números individuales. ^[43]
Lógica modal S5 -Satisfacibilidad
Problema de distancia de clasificación de panqueques para cuerdas ^[44]
Solubilidad de polinomios cuadráticos de dos variables sobre los números enteros. ^[45] Dados números enteros positivos , decida la existencia de números enteros positivos tales que $\textstyle A,B,C$ $x,y$ $Hacha^{2}+By-C=0$
Por el mismo artículo ^[45] existencia de raíces cuadradas modulares acotadas con módulo arbitrariamente compuesto. Dados números enteros positivos , decida 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}}$ $B$
Creación de instancias de segundo orden ^{[ cita necesaria ]}
Serializabilidad de los historiales de bases de datos ^[3]^{: SR33}
Cobertura del set (también llamado problema de cobertura mínima ) Esto equivale, transponiendo la matriz de incidencia, al problema del set de bateo. ^[2]^[3]^{: SP5, SP8}
Establecer embalaje ^[2]^[3]^{: SP3}
Establecer problema de división ^[3]^{: SP4}
Programación para minimizar el tiempo de finalización ponderado
Clasificación de bloques ^[46] (Clasificación por movimientos de bloque)
Aproximación escasa
Variaciones del problema del árbol de Steiner . En concreto, con la métrica euclidiana discretizada, métrica rectilínea. Se sabe que el problema es NP-difícil con la métrica euclidiana (no discretizada). ^[3]^{: ND13}
Modelo tridimensional de Ising ^[47]

Ver 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, Martín; Nikoloski, Zoran; Wagner, Dorothea (2006), Maximizar la modularidad es difícil , arXiv : física/0608255 , Bibcode : 2006física...8255B
^ ab 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 rectilínea y ascendente". Apuntes de conferencias sobre informática . vol. 894/1995. págs. 286–297. doi :10.1007/3-540-58950-3_384. ISBN 978-3-540-58950-1.
^ Schaefer, Marco; Sedgwick, Eric; Štefankovič, Daniel (septiembre de 2003). "Reconocer gráficos de cadenas en NP". Revista de Ciencias de la Computación y de Sistemas . 67 (2): 365–380. doi : 10.1016/S0022-0000(03)00045-X .
^ Lanctot, J.Kevin; Li, Ming; Mamá, 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 , SEÑOR 1994748
^ Wagner, Robert A. (mayo de 1975). "Sobre la complejidad del problema de corrección extendida de cadena a cadena". Actas del séptimo simposio anual de ACM sobre teoría de la informática - STOC '75 . págs. 218-223. doi : 10.1145/800116.803771. ISBN 9781450374194. S2CID 18705107.
^ Friedman, Erich. "Los rompecabezas de corral son NP completos" (PDF) . Consultado el 17 de agosto de 2021 .
^ Yato, Takauki (2003). Complejidad e integridad de encontrar 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, la suma cruzada y sus otros problemas de solución (ASP)" (PDF) . Consultado el 18 de noviembre de 2018 .
^ Nguyen, Viet-Ha; Perrot, Kevin; Vallet, Mathieu (24 de junio de 2020). "NP-integridad del juego KingdominoTM". Informática Teórica . 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) . Revista de Procesamiento de Información . 20 (3): 694–706. doi :10.2197/ipsjjip.20.694. S2CID 46486962. Archivado desde el original (PDF) el 12 de febrero de 2020.
^ Alexandersson, por; Restadh, Petter (2020). "LaserTank es NP-completo". Aspectos Matemáticos de las Ciencias de la Información y la Computación . Apuntes de conferencias sobre informática. vol. 11989. Publicaciones internacionales Springer. págs. 333–338. arXiv : 1908.05966 . doi :10.1007/978-3-030-43120-4_26. ISBN 978-3-030-43119-8. S2CID 201058355.
^ Cormode, Graham (2004). La dureza del juego de los lemmings, o Oh no, más pruebas de completitud de NP (PDF) .
^ Light Up es NP-completo
^ Friedman, Erich (27 de marzo de 2012). "Pearl Puzzles son NP completos". Archivado desde el original el 4 de febrero de 2012.
^ Kaye (2000)
^ Allan Scott, Ulrike Stege, Iris van Rooij, Es posible que Buscaminas no sea NP completo, pero de todos modos es difícil, The Mathematical Intelligencer 33 :4 (2011), págs.
^ Holzer, Markus; Klein, Andreas; Kutrib, Martín (2004). "Sobre la integridad NP del rompecabezas de lápiz NURIKABE y sus variantes" (PDF) . Actas de la 3ª Conferencia Internacional sobre Diversión con Algoritmos . S2CID 16082806. Archivado desde el original (PDF) el 11 de febrero de 2020. {{cite journal}}: Enlace externo en |journal=( ayuda )
^ 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 forma óptima es NP-completo . 35º Simposio sobre Aspectos Teóricos de la Informática (STACS 2018). doi :10.4230/LIPIcs.STACS.2018.24.
^ Chaudhuri, Kamalika; Godfrey, Ilumina; Ratajczak, David; Pequeño, Hoeteck (2003). «Sobre la Complejidad del Juego de Set» (PDF) . {{cite journal}}: Citar diario requiere |journal=( ayuda )
^ ab Sato, Takayuki; Seta, Takahiro (1987). Complejidad e integridad de encontrar otra solución y su aplicación a los rompecabezas (PDF) . Simposio Internacional sobre Algoritmos (SIGAL 1987).
^ Nukui; Uejima (marzo de 2007). "ASP: integridad del rompecabezas Slither Link en varias cuadrículas". Notas de Ipsj Sig . 2007 (23): 129-136.
^ Kölker, Jonas (2012). "Las variantes seleccionadas de Slither Link son NP completas". Revista de Procesamiento de Información . 20 (3): 709–712. doi : 10.2197/ipsjjip.20.709 .
^ Abel, Z.; Demaine, ED; Demaine, ML; Eisenstat, S.; Lynch, J.; Schardl, tuberculosis (2013). "Es difícil encontrar un camino hamiltoniano en un cubo con giros específicos". Revista de Procesamiento de Información . 21 (3): 368–377 . Consultado el 13 de febrero de 2024 .
^ UNA ENCUESTA DE ROMPECABEZAS NP-COMPLETOS, Sección 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; Marzo de 2008. (icga2008.pdf)
^ Demaine, Eric D.; Hohenberger, Susan; Liben-Nowell, David (25 a 28 de julio de 2003). El Tetris es difícil, incluso aproximado (PDF) . Actas de la novena Conferencia Internacional de Computación y Combinatoria (COCOON 2003). Gran cielo, Montana.
^ Lim, Andrew (1998), "El problema de la planificación del atraque", Operations Research Letters , 22 (2–3): 105–110, doi :10.1016/S0167-6377(98)00010-8, MR 1653377
^ J. Bonneau, "La minería de Bitcoin es NP-duro"
^ Galil, Zvi; Meguido, Nimrod (octubre de 1977). "El pedido cíclico es NP completo". Informática Teórica . 5 (2): 179–182. doi : 10.1016/0304-3975(77)90005-6 .
^ Whitfield, James Daniel; Con cariño, Pedro Juan; Aspuru-Guzik, Alán (2013). "Complejidad computacional en estructura electrónica". Física. Química. Química. Física . 15 (2): 397–411. arXiv : 1208.3334 . Código Bib : 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 ACM sobre teoría de la informática . STOC '02. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 761–766. arXiv : matemáticas/0205057 . doi :10.1145/509907.510016. ISBN 978-1-58113-495-7. S2CID 10401375.
^ "Copia archivada" (PDF) . www.meliksah.edu.tr . Archivado desde el original (PDF) el 3 de febrero de 2015 . Consultado el 12 de enero de 2022 .{{cite web}}: Mantenimiento CS1: copia archivada como título ( enlace )
^ Peter Downey, Benton Leong y Ravi Sethi. "Cálculo de secuencias con cadenas de suma" 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 prefijo en cadenas binarias y ternarias". SIAM J. Matemáticas discretas . 21 (3): 592–611. arXiv : matemáticas/0602456 . doi :10.1137/060664252.
^ ab Manders, Kenneth; Adleman, Leonard (1976). "Problemas de decisión NP-completo para polinomios cuadráticos". Actas del octavo simposio anual de ACM sobre teoría de la informática: STOC '76 . págs. 23-29. doi : 10.1145/800113.803627. ISBN 9781450374149. S2CID 18885088.
^ Bein, WW; Larmore, LL; Latifi, S.; Sudborough, IH (1 de enero de 2002). "La clasificación de bloques es difícil". Actas del Simposio Internacional sobre Arquitecturas, Algoritmos y Redes Paralelas. I-SPAN'02 . págs. 307–312. doi :10.1109/ISPAN.2002.1004305. ISBN 978-0-7695-1579-3. S2CID 32222403.
^ Barry Arthur Cipra , "El modelo Ising es NP-completo", SIAM News, Vol 33, No 6.

Referencias

General

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 .
Karp, Richard M. (1972). "Reducibilidad entre problemas combinatorios". En Miller, Raymond E.; Thatcher, James W. (eds.). Complejidad de los cálculos informáticos . Asamblea plenaria. 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. "Problemas NP-completos". Proyecto de referencia de matemáticas . Consultado el 21 de junio de 2008 .

Problemas específicos

Friedman, E (2002). "Los rompecabezas de perlas son NP completos". Universidad Stetson, 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 gráficos integrables con pocos cruces por arista". Algorítmica . 49 (1): 1–11. CiteSeerX 10.1.1.61.3576 . doi :10.1007/s00453-007-0010-x. SEÑOR 2344391. S2CID 8174422.
Hartung, S; Nichterlein, A (2012). "NP-Dureza y trazabilidad de parámetros fijos de la realización de secuencias de grados con gráficos acíclicos dirigidos". Cómo se calcula el mundo . Apuntes de conferencias sobre 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. S2CID 6112925.
Holzer, Markus; Ruepp, Oliver (2007). "Los problemas del diseño de interiores: un análisis de la complejidad del juego Heyawake" (PDF) . Actas, Cuarta Conferencia Internacional sobre Diversión con Algoritmos, LNCS 4475 . Springer, Berlín/Heidelberg. págs. 198-212. doi :10.1007/978-3-540-72914-3_18. ISBN 978-3-540-72913-6.
Kaye, Richard (2000). "Buscaminas es NP completo". Inteligencia Matemática . 22 (2): 9-15. doi :10.1007/BF03025367. S2CID 122435790.Más información disponible en línea en las páginas del Buscaminas de Richard Kaye.
Kashiwabara, T.; Fujisawa, T. (1979). "NP-completitud del problema de encontrar un gráfico de intervalo de número de camarilla mínimo que contenga un gráfico dado como subgrafo". Procedimientos . Simposio Internacional sobre Circuitos y Sistemas . págs. 657–660.
Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979). "Gráficos de intervalo y asignación de puertas lógicas unidimensionales". Transacciones IEEE sobre circuitos y sistemas . 26 (9): 675–684. doi :10.1109/TCS.1979.1084695.
Lengauer, Thomas (1981). "Guijarros blancos y negros y separación de gráficos". Acta Informática . 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 de Métodos Algebraicos y Discretos . 8 (2): 277–284. doi :10.1137/0608024.
Cormode, Graham (2004). "La dureza del juego de los lemmings, o Oh no, más pruebas de completitud NP". Actas de la Tercera Conferencia Internacional sobre Diversión con Algoritmos (FUN 2004) . págs. 65–76.

enlaces externos

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