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 demostrar que hay 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 , mostrando así 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 21 problemas de Karp se muestran a continuación, 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 .
Con el paso del tiempo se descubrió que muchos de los problemas pueden resolverse eficientemente si se restringen a casos especiales, o pueden resolverse 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 mostrar que el enfoque de reducción de Karp se generaliza a un tipo específico de reducción de aproximabilidad. [3] 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).