Los 21 problemas NP-complete Karp marcaron un hito en la historia de la teoría de la complejidad de los algoritmos . Estos son 21 problemas conocidos por ser difíciles en combinatoria y teoría de grafos que son reducibles entre ellos. Esto fue demostrado por Richard Karp en 1972 en su artículo reducibilidad entre problemas combinatorios , así como su NP-completitud.
Uno de los resultados más importantes de la teoría de la complejidad es el de Stephen Cook en 1971 . En su artículo, muestra el primer problema NP-completo , a saber, el problema SAT (ver teorema de Cook ). Es esta idea la que desarrolla Karp aplicándola a problemas combinatorios y de teoría de grafos.
Los 21 problemas están organizados en sangrías para indicar la dirección de la reducción utilizada para demostrar su NP-completitud. Por ejemplo, se ha demostrado que el problema de la mochila es NP-completo mediante una reducción del de la cobertura exacta .
El nombre original en inglés está en mayúsculas.