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.)