Los 21 problemas NP-completos de Karp

En la teoría de la complejidad computacional , los 21 problemas NP-completos de Karp son un conjunto de problemas computacionales que son NP-completos . En su artículo de 1972, "Reducibilidad entre problemas combinatorios", ^[1] Richard Karp utilizó el teorema de Stephen Cook de 1971 de que el problema de satisfacibilidad booleano es NP-completo ^[2] (también llamado teorema de Cook-Levin ) para mostrar que existe una reducción de muchos a uno en tiempo polinomial del problema de satisfacibilidad booleano a cada uno de los 21 problemas computacionales combinatorios y teóricos de grafos , mostrando así que todos son NP-completos. Esta fue una de las primeras demostraciones de que muchos problemas computacionales naturales que ocurren en toda la ciencia de la computación son computacionalmente intratables , y generó interés en el estudio de la NP-completitud y el problema P versus NP .

A continuación se muestran los 21 problemas de Karp, muchos de ellos con sus nombres originales. La anidación indica la dirección de las reducciones utilizadas. Por ejemplo, se demostró que Knapsack era NP-completo al reducir la cobertura Exact a Knapsack .

• Satisfacibilidad : el problema de satisfacibilidad booleana para fórmulas en forma normal conjuntiva (a menudo denominada SAT)
  • Programación entera 0-1 (Una variación en la que solo se deben satisfacer las restricciones, sin optimización)
  • Camarilla (ver también problema de conjuntos independientes )
    • Conjunto de embalaje
    • Cobertura de vértice
      • Cobertura del conjunto
      • Conjunto de nodos de retroalimentación
      • Conjunto de arco de retroalimentación
      • Circuito de Hamilton dirigido (nombre de Karp, ahora llamado habitualmente ciclo hamiltoniano dirigido )
        • Circuito de Hamilton no dirigido (nombre de Karp, ahora llamado habitualmente ciclo hamiltoniano no dirigido )
  • Satisfacción con un máximo de 3 literales por cláusula (equivalente a 3-SAT)
    • Número cromático (también llamado problema de coloración de gráficos )
      • Cobertura de camarilla
      • Cobertura exacta
        • Juego de bateo
        • Árbol de Steiner
        • Coincidencia tridimensional
        • Mochila (la definición de Mochila de Karp se acerca más a la suma de subconjuntos )
          • Secuenciación de trabajos
          • Dividir
            • Corte máximo

Con el tiempo se descubrió que muchos de los problemas se pueden resolver de manera eficiente si se limitan a casos especiales, o se pueden resolver dentro de un porcentaje fijo del resultado óptimo. Sin embargo, David Zuckerman demostró en 1996 que cada uno de estos 21 problemas tiene una versión de optimización restringida que es imposible de aproximar dentro de cualquier factor constante a menos que P = NP, al demostrar que el enfoque de Karp para la reducción se generaliza a un tipo específico de reducción de aproximabilidad. ^[3] Sin embargo, tenga en cuenta que estos pueden ser diferentes de las versiones de optimización estándar de los problemas, que pueden tener algoritmos de aproximación (como en el caso del corte máximo).

• Lista de problemas NP-completos

• Cook, Stephen (1971). "La complejidad de los procedimientos de demostración de teoremas". Proc. 3.er Simposio anual de la ACM sobre teoría de la computación (STOC) . pp. 151–158. doi :10.1145/800157.805047. ISBN. 9781450374644.S2CID 7573663  .
• Karp, Richard M. (1972). "Reducibilidad entre problemas combinatorios" (PDF) . En RE Miller; JW Thatcher; JD Bohlinger (eds.). Complejidad de los cálculos informáticos . Nueva York: Plenum. págs. 85–103. doi :10.1007/978-1-4684-2001-2_9. ISBN. 978-1-4684-2003-6.
• Zuckerman, David (1996). "Sobre versiones inaproximables de problemas NP-completos". Revista SIAM de Computación . 25 (6): 1293–1304. doi :10.1137/S0097539794266407.[1]