human
Je suis tombé sur l'algorithme polynomial qui résout 2SAT. J'ai trouvé cela déconcertant que 2SAT soit dans P alors que toutes (ou beaucoup d'autres) des instances SAT sont NP-Complètes. Qu'est-ce qui rend ce problème différent ? Qu'est-ce qui le rend si facile (NL-Complet - encore plus facile que P)
gpt
Voici une explication supplémentaire intuitive et sans prétention dans la lignée de la réponse de MGwynne.
Avec $2$-SAT, vous ne pouvez exprimer que des implications de la forme $a \Rightarrow b$, où $a$ et $b$ sont des littéraux. Plus précisément, chaque clause $2$-clause $l_1 \lor l_2$ peut être comprise comme une paire d'implications : $\lnot l_1 \Rightarrow l_2$ et $\lnot l_2 \Rightarrow l_1$. Si vous définissez $a$ comme vrai, $b$ doit également être vrai. Si vous définissez $b$ comme faux, $a$ doit également être faux. De telles implications sont simples : il n'y a pas de choix, vous n'avez qu'une seule possibilité, il n'y a pas de place pour la multiplication des cas. Vous pouvez simplement suivre chaque chaîne d'implications possible et voir si vous dérivez à la fois $\lnot l$ de $l$ et $l$ de $\lnot l$ : si vous le faites pour certains $l$, alors la formule 2-SAT n'est pas satisfaisable, sinon elle est satisfaisable. Il est vrai que le nombre de chaînes d'implications possibles est borné de manière polynomiale par la taille de la formule d'entrée.
Avec $3$-SAT, vous pouvez exprimer des implications de la forme $a \Rightarrow b \lor c$, où $a$, $b$ et $c$ sont des littéraux. Maintenant, vous êtes en difficulté : si vous définissez $a$ comme vrai, alors soit $b$ soit $c$ doit être vrai, mais lequel ? Vous devez faire un choix : vous avez 2 possibilités. C'est là que la multiplication des cas devient possible et que l'explosion combinatoire se produit.
En d'autres termes, $3$-SAT est capable d'exprimer la présence de plus d'une possibilité, tandis que $2$-SAT n'a pas cette capacité. C'est précisément cette présence de plus d'une possibilité ($2$ possibilités dans le cas de $3$-SAT, $k-1$ possibilités dans le cas de $k$-SAT) qui provoque l'explosion combinatoire typique des problèmes NP-complets.