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", Richard Karp utilizó el teorema de Stephen Cook de 1971 de que el problema de satisfacibilidad booleano es NP-completo (también llamado teorema de Cook-Levin) para demostrar que hay es una reducción de muchos en tiempo polinómico del problema de satisfacibilidad booleano a cada uno de los 21 problemas computacionales teóricos combinatorios y de gráficos, lo que demuestra que todos son NP-completos. Esta fue una de las primeras demostraciones de que muchos problemas computacionales naturales que ocurren en la informática son computacionalmente intratables, y generó interés en el estudio de la completitud de NP y el problema de P versus NP.

Los problemas

A continuación se muestran los 21 problemas de Karp, muchos de ellos con sus nombres originales. El anidamiento indica la dirección de las reducciones utilizadas. Por ejemplo, se demostró que Knapsack es NP-completo al reducir la Cobertura exacta a Knapsack.

• Satisfiibilidad: el problema de satisfiabilidad booleana para fórmulas en forma conjuntiva normal (a menudo referido como SAT)
  • Programación de enteros 0–1 (Una variación en la que sólo las restricciones deben ser satisfechas, sin optimización)
  • Grupo (véase también el problema establecido independiente)
    • Set packing
    • Cubierta de Vertex
      • Cobertura de conjunto
      • Nodo de comentarios
      • Feedback arc set
      • Circuito directo Hamilton (El nombre de Karp, ahora generalmente llamado Ciclo Hamiltoniano dirigido)
        • Circuito Hamilton no dirigido (El nombre de Karp, ahora generalmente llamado Ciclo Hamiltoniano no dirigido)
  • Satisfiabilidad con al menos 3 literales por cláusula (equivalente a 3-SAT)
    • Número cromático (también llamado Problema de Coloración de Gráficos)
      • Cubierta de la camarilla
      • Cubierta exacta
        • Hitting set
        • Árbol Steiner
        • 3-dimensional matching
        • Knapsack (La definición de Karp de Knapsack está más cerca de la suma de Subset)
          • Secuenciación de empleo
          • Partición
            • Max cortado

Aproximaciones

A medida que pasó el tiempo, se descubrió que muchos de los problemas se pueden resolver de manera eficiente si se restringen a casos especiales, o se pueden resolver 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 mostrar que el enfoque de reducción de Karp se generaliza a un tipo específico de reducción de la proximidad. Sin embargo, tenga en cuenta que 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).