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 est nommé d'après Stephen Cook et Leonid Levin.