Veja Teorema de Cook-Levin na Wikipedia.
S. Cook, The complexity of theorem-proving procedures, Proceedings of the 3rd Symposium on the Theory of Computing, ACM, pp.151-158. 1971.
L. Levin,
Universal Search Problems,
Problemy Peredachi Informatsii. 9(3),
1973.
(Veja também Annals of the History of Computing, 6(4), pp.384-400, 1984.)