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 .
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 un 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).