3-SAT

La question que nous sommes amenés à nous poser maintenant est : existe-t-il un problème de $NP$ au moins aussi difficile que tous les problèmes de $NP$ ? La réponse est oui.

Théorème 10.4.1 (Cook)   Pour tout $\Pi \in NP$, $\Pi \leq 3-SAT$

Le problème $SAT$ est défini dans la problèmethèque. $3-SAT$ correspond au cas particulier dans lequel toutes les clauses contiennent $3$ littéraux. $3-SAT$ est plus difficile que tous les problèmes de $NP$, cela signifie que s'il était possible de décider $3-SAT$ en temps polynomial, il serait alors possible de décider n'importe quel problème de $NP$ en temps polynomial.