En 1972, Richard Karp llevó esta idea un paso más adelante, demostrando que 21 problemas combinatorios y de teoría de grafos, caracterizados por ser computacionalmente intratables, eran NP-completos.