Lista de problemas NP-completos - List of NP-complete problems
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 estos problemas, esta lista no es de ninguna manera exhaustiva. Muchos problemas de este tipo se pueden encontrar en Garey y Johnson (1979) .
Gráficos e hipergráficos
Los gráficos ocurren con frecuencia en las aplicaciones diarias. Los ejemplos incluyen 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
- Coincidencia tridimensional
- Dimensión bipartita
- Árbol de expansión mínimo capacitado
- Problema de inspección de ruta (también llamado problema del cartero chino ) para gráficos mixtos (con bordes tanto dirigidos como no dirigidos). El programa se puede resolver en tiempo polinomial si el gráfico tiene todos los bordes dirigidos o no dirigidos. Las variantes incluyen el problema del cartero rural.
- Problema de camarilla
- Coloración completa , también conocida como número acromático
- Número Domatic
- Conjunto dominante , también conocido como número de dominación
- Los casos especiales NP-completos incluyen el problema del conjunto dominante de bordes , es decir, el problema del conjunto dominante en los gráficos lineales. Las variantes NP-completas incluyen el problema del conjunto dominante conectado y el problema del árbol de expansión máxima de hojas .
- Problema de ancho de banda
- Problema de portada de camarilla
- Coloración de rango también conocido como rango de ciclo
- Árbol de expansión con restricción de grados
- Problema de cobertura exacto . Permanece NP-completo para 3 juegos. Se puede resolver en tiempo polinomial para 2 conjuntos (esto es una coincidencia ).
- Conjunto de vértices de retroalimentación
- Conjunto de arco de retroalimentación
- Problema de homomorfismo gráfico
- Coloración gráfica
- Partición gráfico en subgrafos de tipos específicos (triángulos, isomórficas subgrafos , hamiltonianas subgrafos, bosques , matchings perfectos ) son conocidos NP-completo. La división en grupos 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.
- Finalización hamiltoniana
- Problema del camino hamiltoniano , dirigido y no dirigido.
- Problema del camino más largo
- Máximo subgrafo bipartito o (especialmente con bordes ponderados) corte máximo .
- Conjunto máximo independiente
- Camino inducido máximo
- Número de intersección del gráfico
- Dimensión métrica de un gráfico
- K-corte mínimo
- Árbol de Steiner o árbol de expansión mínimo para un subconjunto de los vértices de un gráfico. (El árbol de expansión mínimo para un gráfico completo se puede resolver en tiempo polinomial).
- Maximización de la modularidad
- Ancho de ruta
- Cobertura del conjunto (también llamado problema de cobertura mínima ) Esto es equivalente, al trasponer la matriz de incidencia, al problema del conjunto de golpes.
- Establecer problema de división
- Árbol de expansión de longitud de ruta total más corta
- Prueba de pendiente número dos
- Ancho de árbol
- Cubierta de vértice
Programación matemática
- Problema de 3 particiones
- Problema de embalaje del contenedor
- Problema de la mochila , problema de la mochila cuadrática , y varias variantes
- Variaciones sobre el problema del viajante . El problema de las gráficas es NP-completo si las longitudes de los bordes se suponen enteros. El problema para los 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).
- Vendedor ambulante de cuello de botella
- Programación de enteros . 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-completas
- Cuadrados latinos (el problema de determinar si un cuadrado parcialmente lleno se puede completar para formar uno)
- Coincidencia numérica tridimensional
- Problema de partición
- Problema de asignación cuadrática
- Resolver polinomios cuadráticos de dos variables sobre números enteros. Dados números enteros positivos , encuentre números enteros positivos tales que
- Programación cuadrática (NP-duro en algunos casos, P si es convexo)
- Problema de suma de subconjuntos
Lenguajes formales y procesamiento de cadenas
- Cadena más cercana
- Problema de subsecuencia común más largo en múltiples secuencias
- La variante acotada del problema de correspondencia postal
- Supersecuencia común más corta
- Problema de corrección de cuerda a cuerda
Juegos y rompecabezas
- Bolsa (Corral)
- Acorazado
- Bulls and Cows , comercializado como Master Mind : ciertos problemas de optimización pero no el juego en sí.
- Eternidad II
- ( Generalizado ) FreeCell
- Fillomino
- Hashiwokakero
- Heyawake
- ( Generalizado ) Locura instantánea
- Kakuro (Sumas cruzadas)
- Kingdomino
- Kuromasu (también conocido como Kurodoko)
- LaserTank
- Lemmings (con un límite de tiempo polinomial)
- Encender
- Masyu
- Problema de consistencia del buscaminas (pero ver Scott, Stege y van Rooij)
- Nimber (o número de Grundy) de un gráfico dirigido.
- Numberlink
- Nonogramas
- Nurikabe
- Pandemia ( generalizada )
- Solución óptima para el cubo de Rubik N × N × N
- Mismo juego
- ( Generalizado ) Conjunto
- Slither Link en una variedad de cuadrículas
- ( Generalizado ) Sudoku
- Show de Tentai
- Problemas relacionados con el Tetris
- Aritmética verbal
Otro
- Problema de asignación de literas
- Intermediación
- Montaje de un bloque Bitcoin óptimo .
- Problema de satisfacibilidad booleano (SAT). Hay muchas variaciones que también son NP-completas. Una variante importante es donde cada cláusula tiene exactamente tres literales (3SAT), ya que se usa en la prueba de muchos otros resultados de NP-completitud.
- Consulta booleana conjuntiva
- Orden cíclico
- Problema de satisfacibilidad del circuito
- Problema de ubicación de instalaciones no capacitadas
- Problema de programación de Flow Shop
- Problema de asignación generalizado
- Prueba de planaridad ascendente
- Encontrar la solución mínimo global de un método de Hartree-Fock problema
- Problema de los hospitales y los residentes con las parejas
- Algunos problemas relacionados con la programación del taller de trabajo
- Triángulo monocromático
- Conjunto mínimo máximo independiente también conocido como conjunto dominante mínimo independiente
- Los casos especiales NP-completos incluyen el problema de emparejamiento mínimo máximo , que es esencialmente igual al problema del conjunto que domina el borde (ver arriba).
- Problema de isomorfismo de subgrafo común máximo
- Árbol de expansión de grado mínimo
- Árbol de extensión k mínimo
- Centro k métrico
- Máxima 2-Satisfacción
- Lógica modal S5-Satisfacción
- Algunos problemas relacionados con la programación del multiprocesador
- Máximo volumen submatriz - problema de seleccionar el mejor subconjunto condicionado de una más grande de la matriz. Esta clase de problema está asociada con las factorizaciones QR que revelan el rango y el diseño experimental óptimo D.
- Cadenas de suma mínima para secuencias. Se desconoce la complejidad de las cadenas de suma mínima para números individuales.
- Polinomios univariados no lineales sobre GF [2 n ], n la longitud de la entrada. De hecho, sobre cualquier GF [q n ].
- Programación de tienda abierta
- Ancho de ruta o, de manera equivalente, espesor de intervalo y número de separación de vértices
- Problema de distancia de clasificación de panqueques para cuerdas
- cartero k-chino
- Problema de isomorfismo de subgrafo
- Variaciones del problema del árbol de Steiner . Específicamente, 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).
- Establecer embalaje
- Serializabilidad de los historiales de la base de datos
- Programación para minimizar el tiempo de finalización ponderado
- Aproximación escasa
- Clasificación de bloques (clasificación por movimientos de bloques)
- Creación de instancias de segundo orden
- Ancho de árbol
- Prueba de si un árbol puede representarse como árbol de expansión mínimo euclidiano
- Modelo de Ising tridimensional
- Problema de ruta del vehículo
Ver también
- Teoría existencial de los reales # Problemas completos
- Los 21 problemas NP-completos de Karp
- Lista de problemas completos de PSPACE
- Reducción (complejidad)
Notas
Referencias
General
- Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , W. H. Freeman , ISBN 0-7167-1045-5. Este libro es un clásico, desarrolla la teoría y luego cataloga muchos problemas NP-Complete.
- 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 matemática . Consultado el 21 de junio de 2008 .
Problemas específicos
- Friedman, E (2002). "Los rompecabezas de perlas son NP-completos" . Universidad Stetson, DeLand, Florida . Consultado el 21 de junio de 2008 .
- Grigoriev, A; Bodlaender, HL (2007). "Algoritmos para gráficos incrustables con pocos cruces por borde". Algoritmica . 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). Cómo se calcula el mundo . Apuntes de conferencias en Ciencias de la Computación. 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, 4ta 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". Intelligencer matemático . 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 mínimo de clique que contenga un gráfico dado como un subgráfico". Actas . Simposio Internacional de 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 puerta lógica unidimensional". Transacciones IEEE en circuitos y sistemas . 26 (9): 675–684. doi : 10.1109 / TCS.1979.1084695 .
- Lengauer, Thomas (1981). "Guijarros blanco y negro y separación de gráficos". 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 de Métodos Algebraicos y Discretos . 8 (2): 277–284. doi : 10.1137 / 0608024 .
- Cormode, Graham (2004). "La dureza del juego de los lemmings, u Oh no, más pruebas de NP-completitud". Actas de la Tercera Conferencia Internacional sobre Diversión con Algoritmos (FUN 2004) . págs. 65–76.