C'est-à-dire que tout problème dans le NP peut être réduit en temps polynomial par une machine déterministe de Turing au problème de déterminer si une formule booléenne est satisfaisante.
Le théorème Cook -- Levin est un théorème de l'informatique théorique, qui dit que le problème de satisfabilité booléenne est NP-complet.