La demostración fue elaborada en 1972 por el informático teórico Richard Karp, en su trabajo seminal "Reducibility Among Combinatorial Problems" (Reducibilidad entre Problemas Combinatorios),[1] como profundización del trabajo de Stephen Cook, quien en 1971 había demostrado uno de los resultados más importantes y pioneros de la complejidad computacional: la NP-completitud del problema de satisfacibilidad booleana.
Mientras que la pertenencia del problema SAT o de satisfacibilidad booleana a la clase de los NP-completos fue demostrada utilizando mecanismos particulares, las pertenencias de los 21 problemas siguientes fueron demostradas mediante reducciones polinomiales.
La lista completa es la que se muestra a continuación.
Note que los nombres de los problemas están escritos con letras mayúsculas y corresponden a abreviaciones del nombre en inglés, como es lo usual; junto a ellos, entre paréntesis, se escribe la traducción del nombre en español.
Tras un tiempo se descubrió que muchos de estos problemas podían ser resueltos si su enunciado se particularizaba a unas ciertas clases, o podían ser resueltos aproximadamente con un error máximo de un cierto porcentaje.