Richard Karp, en la Universidad de California en Berkeley, publica en 1972 "Reducibility Among Combinatorial Problems", donde toma el resultado de Stephen Cook de 1971 —que establece la existencia de problemas NP-completos mediante el caso de la satisfacibilidad booleana— y demuestra que otros veintiún problemas combinatorios clásicos, de apariencia completamente distinta entre sí, son también NP-completos: el problema del viajante (encontrar la ruta más corta que visite un conjunto de ciudades exactamente una vez), el coloreado de grafos, la mochila, el conjunto independiente máximo y muchos otros. La técnica que emplea Karp —reducir un problema a otro mediante transformaciones que preservan la dificultad computacional— se convierte en el método estándar para clasificar nuevos problemas como NP-completos sin necesidad de probar directamente su dificultad desde cero: basta demostrar que un problema conocido se puede traducir al nuevo problema en tiempo polinómico. El artículo transforma la NP-completitud de una curiosidad teórica aislada en una propiedad estructural extendida por toda la informática práctica: miles de problemas de optimización en logística, planificación, diseño de redes y biología computacional resultan ser NP-completos, lo que explica por qué en la práctica se recurre a algoritmos aproximados o heurísticos en lugar de buscar soluciones exactas garantizadas.