Anexo:Problemas NP-completos
Esta es una lista de algunos de los problemas más comúnmente conocidos que se NP-completo Cuando se expresa como problema de decisión. Como hay cientos de estos problemas conocidos, esta lista no es de ninguna manera exhaustiva. Muchos de los problemas de este tipo se pueden encontrar en Garey y Johnson (1979).
- Esta es una lista incompleta, que nunca puede ser capaz de satisfacer las normas particulares para la integridad. Usted puede ayudar ampliándola con entradas que se pueden adquirir de manera fiable.
Grafos y hypergrafos[editar]
Grafos se producen con frecuencia en aplicaciones de uso diario. Los ejemplos incluyen las redes biológicas o sociales, que contienen cientos, miles e incluso miles de millones de nodos en algunos casos (ver por ejemplo Facebook o LinkedIn).
- 1-planaridad[1]
- Juego de 3 dimensiones[2][3]
- Dimensión Bipartita[4]
- Árboles de costo mínimo[5]
- Problema de inspección de ruta (también llamado 'problema del cartero chino' ) para grafos mixtos (teniendo ambos arcos dirigidos y no dirigidos). El programa es resoluble en tiempo polinomial si el grafo tiene todos los arcos dirigidos o todos no dirigido. Las variantes incluyen el problema cartero rural[6]
- Problema del Clique[2][7]
- Coloración completa, número cromático[8]
- Número de Domatic[9]
- Dominando set, también conocido como número dominación[10]
- Casos especiales NP-completos incluyen la desequilibrante borde set problema, es decir, el conjunto de problemas dominante en Grafos de líneas. Variantes NP-completos incluyen la desequilibrante conectado ajustada problema y la [árbol] [máximo de hoja que abarca] problema[11]
- Problema ancho de banda[12]
- Problema de cobertura de Clique[2][13]
- Rango de coloración
- Grado con limitaciones(árbol abarcador)[14]
- Problema de Cobertura exacta. NP-completo para 3 conjuntos. Solubles en tiempo polinómico para 2 conjuntos (este es un juego)[2]Garey y Johnson (1979):. SP2 </ref>
- Retroalimentación con conjunto de vértices[2][15]
- Retroalimentación con conjunto de arcos[2][16]
- Problema de Grafos homomorfos[17]
- Coloración de Grafos[2][18]
- Partición de Grafos en subgrafos de tipos específicos (triángulos, isomorfo subgrafos, hamiltoniano subgrafos, bosques, juego perfecto s) se conocen NP-completo. Partición en camarillas es el mismo problema que colorear de complementar del Grafo dado. Un problema relacionado es encontrar una partición que es términos óptimos de la cantidad de arcos entre las partes[19]
- Finalización de Hamilton[20]
- Problema del camino hamiltoniano, dirigida y no dirigida[2][21]
- Problema del camino máximo[22]
- Subgrafo máximo bipartito o (especialmente con arcos ponderados) máxima corte[2][23]
- Conjunto independiente máximo[24]
- Máxima ruta inducida[25]
- número de intersección del Grafo[26]
- Acotado métrico de un Grafo[27]
- K-corte mínimo
- árbol de expansión mínimo., O árbol de Steiner, para un subconjunto de los vértices de un grafo[2] (El árbol de expansión mínima de un Grafo de todo es solucionable en tiempo polinómico).
- Problema del camino ancho[28]
- Conjunto de cubierta (también llamado 'cobertura mínima' problema) Esto es equivalente, mediante la transposición de la matriz de incidencia, para el conjunto de problemas que golpea[2] <. ref>[29]: SP5, SP8 </ref>
- Problema de división de conjuntos[30]
- Longitud del camino más corto en árboles abarcadores[31]
- Número pendiente dos pruebas[32]
- Ancho de árboles[28]
- Cubierta de vértices[2][33]
La programación matemática[editar]
- Problema 3-partición[34]
- Problema de Embalaje[35]
- Problema de la mochila y varias variantes[2][36]
- Variaciones sobre el problema del viajante. El problema para los Grafos es NP-completo si las longitudes de los arcos son enteros asumidos. El problema para los puntos en el plano es NP-completo con la métrica y rectilínea euclidiana discretizado. El problema es conocido por ser NP-duro con el (discretizado no) euclidiana métricas[37]
- Cuello de botella del viajante[38]
- Programación entera. La variante donde se requieren las variables a ser 0 o 1, llamada programación lineal cero-uno, y varias otras variantes también son NP-completo[2][39]
- Numérical juego de 3 dimensiones[40]
- Problema de reparto[2][41]
- Problema de asignación cuadrática[42]
- Programación cuadrática (NP-difícil en algunos casos, si P convexo)
- Problema de la suma de subconjuntos[43]
Los lenguajes formales y procesamiento de cadenas[editar]
- Cadena más cercana[44]
- Problema de subsecuencia común mayor[45]
- La variante acotada del problema de correspondencia de mensajes[46]
- Supersecuencia común más corta[47]
- Problema de corrección cadena a cadena[48]
Juegos y rompecabezas[editar]
- Batalla Naval
- Adornado con joyas[49]
- Toros y Vacas, comercializados como Mente Maestra
- Saga Candy Crush[50][49]
- Eternidad II
- (Generalizada) Carta blanca[51]
- Fillomino[52]
- Heyawake[53]
- (Generalizada) Locura inmediata[54]
- Kakuro (sumas cruzadas)
- Kuromasu (también conocido como Kurodoko)[55]
- Lemmings[56]
- Enciéndase[57]
- Masyu[58]
- Problema del Buscaminas[59] (pero véase Scott, Stege, y van Rooij[60])..
- Nimber (o número de Grundy) de un grafo dirigido[61]
- Nonogramas
- Nurikabe
- SameGame
- Conexión deslizante en una variedad de redes[62][63][64][65]
- (Generalizada) Sudoku
- Super Mario Bros[66]
- Los problemas relacionados con Tetris[67]
- Aritmética verbal
Otros[editar]
- Problema de la galería de arte y sus variaciones.
- Problema de asignación de amarre[68]
- Montaje de un Bitcoin bloque óptima.[69]
- Problema satisfacción booleana (SAT)[2][70] Hay muchas variaciones que también son NP completo. Una variante importante es donde cada cláusula tiene exactamente tres literales (3SAT), ya que se utiliza en la prueba de muchos otros resultados NP-completos.[71]
- Consulta booleana en forma conjuntiva[72]
- Ordenamiento cíclico
- Problema de satisfacción de circuitos
- Incapacidad sobre la Ubicación
- Problema de planificación de circulación
- Problema de asignación generalizada
- Prueba de planaridad hacia arriba [32]
- Algunos de los problemas relacionados con la planificación
- Triángulo Monocromático[73]
- Conjunto independiente mínimo mínimo conjunto dominante independiente[74]
- Casos especiales NP-completos incluyen el problema de mínimo acoplamiento,[75] que es esencialmente igual al problema del conjunto dominante de aristas (véase más arriba).
- Problema del subgrafo isomorfo máximo[76]
- Grado mínimo de un árbol abarcador
- K-árbol abarcador mínimo
- Métricas k-centro
- Máximo 2-satisfacibilidad[77]
- Lógica modal S5-satisfacibilidad
- Algunos de los problemas relacionados con la programación multiprocesador
- Volumen máximo de una submatriz - problema de seleccionar el subconjunto de una matriz mxn más grande mejor acondicionado. Esta clase de problema se asocia con Rango revelando factorizaciones QR s y D de diseño experimental óptimo.[78]
- Cadena de adición mínimas para las secuencias.[79] La complejidad de las cadenas de adición mínimos para números individuales es desconocido[80]
- Polinomios no lineales invariantes sobre grafos [2 n </ sup>], n la longitud de la entrada. En efecto sobre cualquier grafo [q n </ sup>].
- Planificación de horarios en tiendas
- Ancho de un camino,[81] o, equivalentemente, intervalo de espesor y número de separación de vértices[82]
- Clasificación Pancake problema de la distancia para las cadenas[83]
- Problema del k-cartero Chino
- Problema de subgrafos isomorfos[84]
- Las variaciones del problema del árbol de Steiner. En concreto, con la métrica rectilínea euclidiana discretizada. El problema es conocido por ser NP-duro con la métrica euclidiana no discretizada.[85]
- Establecer embalaje[2][86]
- Serialización de bases de datos de historias[87]
- Planificación para minimizar el tiempo de finalización ponderada
- Aproximación escasa
- Bloquear Clasificación (Clasificación por movimientos de bloques)
- Particularización de segundo orden
- Ancho de árbol[81]
- Comprobar que un árbol puede representarse como árbol abarcador de costo mínimo euclidiano
- Modelo tridimensional Ising[88]
- Problema de ruteo de vehículos
<! - Problemas de lógica proposicional, en particular, los problemas de satisfacibilidad y sus variantes, son de particular interés práctico porque muchos problemas prácticos pueden ser resueltos por expresarlos como problemas satisfacibilidad, y luego utilizando eficientes SAT solver s para obtener una exacta solución rápida [cita requerida] .-->
Véase también[editar]
Notas[editar]
- ↑ Grigoriev y Bodlaender , 2007.
- ↑ a b c d e f g h i j k l m n ñ o p Karp ( 1972)
- ↑ : SP1
- ↑ : GT18
- ↑ : ND5
- ↑ :. ND25, ND27
- ↑ : GT19
- ↑ : GT5
- ↑ : GT3
- ↑ : GT2
- ↑ :. ND2
- ↑ : GT40
- ↑ : GT17
- ↑ : ND1
- ↑ : GT7
- ↑ : GT8
- ↑ : GT52
- ↑ : GT4
- ↑ :. GT11, GT12, GT13, GT14, GT15, GT16, ND14
- ↑ : GT34
- ↑ :. GT37, GT38, GT39
- ↑ : ND29
- ↑ :. GT25, ND16
- ↑ : GT20
- ↑ : GT23
- ↑ : GT59
- ↑ : GT61
- ↑ a b Arnborg , Corneil y Proskurowski ( 1987)
- ↑ Garey y Johnson, 1979.
- ↑ : SP4
- ↑ : ND3
- ↑ a b «En la complejidad computacional de pruebas planaridad hacia arriba y rectilínea». la conferencia en Ciencias de la Computación. 894/1995. 1995. pp. 286-297. doi:10.1007/3-540-58950-3_384.
- ↑ : GT1
- ↑ : SP15
- ↑ : SR1
- ↑ : MP9
- ↑ :. ND22, ND23
- ↑ : ND24
- ↑ {{harvtxt | Garey | Johnson | 1979} }: MP1
- ↑ : SP16
- ↑ : SP12
- ↑ : ND43
- ↑ : SP13
- ↑ Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003). «Problemas de selección de cadena Distinción». Informáticos y Computación 185 (1): 41-55. MR 1994748. doi:10.1016/S0890-5401(03)00057-9.
- ↑ : SR10
- ↑ : SR11
- ↑ : SR8
- ↑ : SR20
- ↑ a b L. Guala, S. Leucci, E. Natale (2014). «Bejeweled, Crush Candy y otros partido y tres juegos son (NP) duro».
- ↑ Walsh, Toby (2014). «caramelo Crush es NP-hard».
- ↑ Malte Helmert, resultados de complejidad para los dominios de referencia estándar en la planificación, la Inteligencia Artificial Diario 143 (2):. 219-262, 2003
- ↑ Yato, Takauki (2003). «Complejidad e Integridad de encontrar otra solución y su Aplicación al Puzzles».
- ↑ Holzer y Ruepp ( 2007)
- ↑ : GP15
- ↑ Kölker, Jonas (2012). [https: / /www.jstage.jst.go.jp/article/ipsjjip/20/3/20_694/_article Kurodoko es NP-completo].
- ↑ Cormode, Graham (2004). La dureza del juego lemmings, o ¡Oh, no, más pruebas NP-completitud.
- ↑ Light Up es NP-completo
- ↑ Friedman, Erich (27 de marzo de 2012). /pearl/pearl.html «Perla Puzzles son NP-completo».
- ↑ Kaye ( 2000)
- ↑ Allan Scott, Ulrike Stege, Iris van Rooij, Buscaminas no puede ser NP-completo, pero es difícil, sin embargo, The Mathematical Intelligencer '33' : 4 (2011), pp 5-17
- ↑ :. GT56
- ↑ Yato; Seta. Complejidad e Integridad de encontrar otra solución y su aplicación a Puzzles.
- ↑ Yato. .ac.jp / ~ yato / data2 / MasterThesis.pdf «Complejidad e integridad de encontrar otra solución y su aplicación a los rompecabezas».
- ↑ Nukui; Uejima. ASP-Integridad de la Slither Enlace Puzzle en varias cuadrículas.
- ↑ Kölker, Jonas (2012). seleccionado Slither Enlace variantes son NP-completos.
- ↑ G. Aloupis, ED Demaine, A. Guo (9 de marzo de 2012). /pdf/1203.1895v1.pdf «clásicos juegos de Nintendo son (NP) Duro».
- ↑ Demaine, Eric D.; Hohenberger, Susan; Liben-Nowell, David (25 a 28 de julio de 2003). «Tetris es difícil, incluso para Aproximado». Actas de la novena Internacional de Computación y Conferencia Combinatoria (COCOON 2003) (Big Sky, Montana). Archivado desde el original el 5 de enero de 2012.
- ↑ Lim, Andrew (1998). «El problema de planificación litera». Operations Research Letters 22 (2.3): 105-110. MR 1653377. doi:10.1016/S0167-6377(98)00010-8.
- ↑ J. Bonneau, "la minería Bitcoin es NP -Hard
- ↑ :. LO1
- ↑ :. P. 48
- ↑ : SR31
- ↑ : GT6
- ↑ mínimo Dominando Set Independiente
- ↑ : GT10
- ↑ : GT49
- ↑ : OA5
- ↑ http://www.cs.rpi.edu/~civria/max-vol-inapprox.pdf
- ↑ Peter Downey, Benton Leong, y Ravi Sethi. . "Informática Secuencias con Cadenas de adición" SIAM J. Comput, 10 (3), 638-646, 1981
- ↑ [http:. //cr.yp .to / documentos / pippenger.pdf DJ Bernstein, "algoritmo de exponenciación de Pippinger (proyecto)]
- ↑ a b Arnborg , Corneil y Proskurowski ( 1987)
- ↑ Kashiwabara y Fujisawa ( 1979);Ohtsuki et al. ( 1979);Lengauer ( 1981).
- ↑ Hurkens, C., Iersel, LV, Keijsper, J., Kelk, S., Stougie, L. y J. Tromp "reversiones de prefijo en cadenas binarias y ternarias" . SIAM J. Matemática Discreta. 21 (3) (2007) 592-611.
- ↑ : GT48
- ↑ :. ND13
- ↑ : SP3
- ↑ : SR33
- ↑ Barry A. Cipra, "es el modelo de Ising NP-completo", SIAM News, Vol 33, No 6.
<ref> definida en las <references> con nombre «FOOTNOTEGareyJohnson1979» no se utiliza en el texto anterior.Referencias[editar]
- General
- Garey, Michael R.; Johnson, David S. (2009). Computers and intractability: a guide to the theory of NP-completeness. A series of books in the mathematical sciences (27. print edición). New York [u.a]: Freeman. ISBN 978-0-7167-1045-5.. This book is a classic, developing the theory, then cataloguing many NP-Complete problems.
- Cook, S.A. (1971). «The complexity of theorem proving procedures». Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York. pp. 151-158. doi:10.1145/800157.805047.
- Karp, Richard M. (1972). «Reducibility among combinatorial problems». En Miller, Raymond E.; Thatcher, James W., eds. Complexity of Computer Computations. Plenum. pp. 85-103.
- Dunne, P.E. «An annotated list of selected NP-complete problems». COMP202, Dept. of Computer Science, University of Liverpool. Consultado el 21 de junio de 2008.
- Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G. «A compendium of NP optimization problems». KTH NADA, Stockholm. Consultado el 21 de junio de 2008.
- Dahlke, K. «NP-complete problems». Math Reference Project. Consultado el 21 de junio de 2008.
- Specific problems
- Friedman, E (2002). «Pearl puzzles are NP-complete». Stetson University, DeLand, Florida. Consultado el 21 de junio de 2008.
- Grigoriev, A; Bodlaender, H L (2007). «Algorithms for graphs embeddable with few crossings per edge». Algorithmica 49 (1): 1-11. MR 2344391. doi:10.1007/s00453-007-0010-x.
- Hartung, S; Nichterlein, A (2012). «NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs». Springer, Berlin, Heidelberg. Consultado el 24 de enero de 2013.
- Holzer, Markus; Ruepp, Oliver (2007). «The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake». Proceedings, 4th International Conference on Fun with Algorithms, LNCS 4475. Springer, Berlin/Heidelberg. pp. 198-212. ISBN 978-3-540-72913-6. doi:10.1007/978-3-540-72914-3_18.
- Kaye, Richard (2000). «Minesweeper is NP-complete». Mathematical Intelligencer 22 (2): 9-15. doi:10.1007/BF03025367. Further information available online at Richard Kaye's Minesweeper pages.
- Kashiwabara, T.; Fujisawa, T. (1979). «NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph». Proc. International Symposium on Circuits and Systems. pp. 657-660..
- Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979). «One-dimensional logic gate assignment and interval graphs». IEEE Transactions on Circuits and Systems 26 (9): 675-684. doi:10.1109/TCS.1979.1084695..
- Lengauer, Thomas (1981). «Black-white pebbles and graph separation». Acta Informatica 16 (4): 465-475. doi:10.1007/BF00264496..
- Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej (1987). «Complexity of finding embeddings in a k-tree». SIAM Journal on Algebraic and Discrete Methods 8 (2): 277-284. doi:10.1137/0608024..
- Cormode, Graham (2004). «The hardness of the lemmings game, or Oh no, more NP-completeness proofs». Proceedings of Third International Conference on Fun with Algorithms (FUN 2004). pp. 65-76.