O primeiro problema NP-completo

Veja Teorema de Cook-Levin na Wikipedia.

S. CookThe complexity of theorem-proving procedures,  Proceedings of the 3rd Symposium on the Theory of Computing,  ACM,  pp.151-158.  1971.

L. LevinUniversal Search Problems,  Problemy Peredachi Informatsii. 9(3),  1973.  (Veja tambĂ©m Annals of the History of Computing, 6(4), pp.384-400, 1984.)

Valid HTML 4.01 Strict Valid CSS!