Dans la théorie de la complexité computationnelle, le théorème de Cook -- Levin, également connu sous le nom de théorème de Cook, indique que le problème de satisfabilité booléenne est NP-complet.
Sur une machine de Turing déterministe, cela prend du temps polynomial.