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 que establece que el problema de satisfacibilidad booleana es NP-completo ^{[ 2 ]} (también llamado teorema de Cook-Levin ) para demostrar que existe una reducción de muchos a uno en tiempo polinomial del problema de satisfacibilidad booleana a cada uno de los 21 problemas computacionales combinatorios y de teoría de grafos , demostrando así que todos ellos son NP-completos. Esta fue una de las primeras demostraciones de que muchos problemas computacionales naturales que aparecen en toda la ciencia de la computación son computacionalmente intratables , e impulsó el 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 con sus nombres originales. El anidamiento indica la dirección de las reducciones utilizadas. Por ejemplo, se demostró que el problema de la mochila es NP-completo al reducir la cobertura exacta a la mochila .

• Satisfacibilidad : el problema de satisfacibilidad booleana para fórmulas en forma normal conjuntiva (a menudo denominado SAT).
  • Programación entera 0-1 (una variante en la que solo deben cumplirse las restricciones, sin optimización).
  • Camarilla (véase también problema del conjunto independiente )
    • Embalaje del conjunto
    • cobertura de vértices
      • Conjunto que cubre
      • Conjunto de nodos de retroalimentación
      • Conjunto de arcos de retroalimentación
      • Circuito hamiltoniano dirigido (nombre de Karp, ahora generalmente llamado ciclo hamiltoniano dirigido )
        • Circuito hamiltoniano no dirigido (nombre de Karp, ahora generalmente llamado ciclo hamiltoniano no dirigido )
  • Satisfacibilidad 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 grafos )
      • Portada de Clique
      • Cobertura exacta
        • Juego de golpes
        • á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 pueden resolverse de manera eficiente si se restringen a casos especiales, o pueden resolverse dentro de cualquier 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 la aproximabilidad. ^{[ 3 ]} Sin embargo, estas 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» . Actas del 3.er Simposio Anual de la ACM sobre Teoría de la Computación (STOC) . págs. 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. pp. 85–103 . doi : 10.1007/978-1-4684-2001-2_9 . ISBN  978-1-4684-2003-6.{{cite book}}: CS1 mantenimiento: ubicación del editor ( enlace )
• Zuckerman, David (1996). "Sobre versiones inaproximables de problemas NP-completos" . SIAM Journal on Computing . 25 (6): 1293– 1304. doi : 10.1137/S0097539794266407 .