El Teorema de Cook demuestra que el problema de la satisfactibilidad booleana es NP-completo, y de hecho, este fue el primer problema de decisión que se demostró pertenecer a esta clase de problemas.