Karp define la complejidad polinómica y la equivalencia de problemas

Fuentes: Karp defines polynomial complexity and problem equivalence

El artículo 'Reducibility Among Combinatorial Problems', publicado por Richard M. Karp en la Universidad de California en Berkeley en 1972, establece los fundamentos teóricos de la complejidad computacional moderna. Karp define un problema como resuelto satisfactoriamente cuando existe un algoritmo que termina en un número de pasos acotado por un polinomio en la longitud de la entrada. Esta definición introduce la clase P, compuesta por los lenguajes reconocibles en tiempo polinómico por máquinas de Turing deterministas de una cinta, y la clase NP, asociada a las máquinas no deterministas.

La contribución central del trabajo es demostrar que una gran cantidad de problemas combinatorios clásicos, como la cobertura, el emparejamiento, el enrutamiento y la asignación, son equivalentes en el sentido de que poseen un algoritmo de tiempo polinómico si y solo si todos lo poseen. Karp introduce el concepto de problemas completos (complete problems): un problema es completo si pertenece a NP y todo otro problema en NP es reducible a él. El autor demuestra que si un problema completo tiene un algoritmo polinómico, entonces todos los problemas en NP lo tienen, lo que implica que P = NP. Esta investigación, inspirada en el trabajo de Stephen Cook, sentó las bases para la clasificación de la dificultad de los problemas de programación lineal, teoría de grafos y lógica computacional, definiendo la frontera entre los problemas tratables y los intratables.