Pourquoi 2SAT est-il en P?

J'ai rencontré l'algorithme polynomial qui résout 2SAT. J'ai trouvé ahurissant que 2SAT soit dans P où toutes (ou beaucoup d'autres) des instances SAT sont NP-Complete. Qu'est-ce qui rend ce problème différent? Qu'est-ce qui le rend si facile (NL-Complete - encore plus facile que P)?

Voici une autre explication intuitive et sans prétention dans le sens de la réponse de MGwynne.

Avec SAT, vous ne pouvez exprimer que les implications de la forme , où et sont des littéraux. Plus précisément, chaque clause peut être comprise comme une paire d'implications: et . Si vous définissez sur true, doit également être vrai. Si vous définissez sur false, doit être également faux. De telles implications sont simples: il n'y a pas de choix, vous avez seulementa ⇒ b a b 2 L 1 ∨ l 2 ¬ l 1 ⇒ l 2 ¬ l 2 ⇒ l 1 a b b a 1 ¬ l l l ¬ l $2$$a \Rightarrow b$$a$$b$$2$$l_1 \lor l_2$$\lnot l_1 \Rightarrow l_2$$\lnot l_2 \Rightarrow l_1$$a$$b$$b$$a$$1$possibilité, il n'y a pas de place pour la multiplication de cas. Vous pouvez simplement suivre toutes les chaînes d'implication possibles et voir si vous dérivez jamais les deux de et de : si vous le faites pour un , alors la formule 2-SAT est insatisfiable, sinon elle est satisfiable. Il est vrai que le nombre de chaînes d’implication possibles est lié de manière polynomiale à la taille de la formule d’entrée.$\lnot l$$l$$l$$\lnot l$$l$

Avec SAT, vous pouvez exprimer les implications de la forme , où , et sont des littéraux. Maintenant vous êtes en difficulté: si vous définissez sur true, alors soit ou doit être vrai, mais lequel? Vous devez faire un choix: vous avez 2 possibilités. C'est ici que la multiplication de cas devient possible et que l'explosion combinatoire se produit.a ⇒ b ∨ c a b c a b $3$$a \Rightarrow b \lor c$$a$$b$$c$$a$$b$$c$

En d'autres termes, SAT est capable d'exprimer la présence de plus d'une possibilité, alors que SAT n'a pas cette capacité. C'est précisément la présence de plus d'une possibilité ( possibilités dans le cas de SAT, possibilités dans le cas de SAT) qui provoque l'explosion combinatoire typique de problèmes NP-complets.2 2 3 k - 1 $3$$2$$2$$3$$k-1$$k$

$n + m -2 \le 2$$n, m \le 2$$n$$m$

Une fois que vous arrivez à 3-SAT, vous pouvez obtenir des résolutions de plus en plus grandes, ainsi tout se passe en forme de poire :).

Essayez de traduire un problème en 2-SAT. Comme vous ne pouvez pas avoir de clauses de taille 3, vous ne pouvez pas (en général) coder les implications impliquant 3 variables ou plus, par exemple, une variable est le résultat d'une opération binaire sur deux autres. C'est une restriction énorme.

Comme le dit Walter, les clauses de 2-SAT ont une forme spéciale. Cela peut être exploité pour trouver des solutions rapidement.

Il existe en fait plusieurs classes d'instances SAT qui peuvent être décidées en temps polynomial, et 2-SAT n'est qu'une de ces classes traitables . Il existe trois grands types de raisons de la traitabilité:

1. (Traitabilité structurelle) Toute classe d'instances SAT où les variables interagissent de manière arborescente peut être résolue en temps polynomial. Le degré du polynôme dépend de la largeur maximale des occurrences dans la classe, où elle mesure la distance entre une instance et un arbre. Plus précisément, Marx a montré que si les instances ont une largeur sous-modulaire limitée, alors la classe peut être décidée en temps polynomial en utilisant une approche diviser pour mieux régner.

2. (Traitabilité du langage) Toute classe d'instances SAT où le modèle de variables true-false est "sympa", peut être résolue en temps polynomial. Plus précisément, le modèle de littéraux définit un langage de relations et Schaefer a classé les six langages qui conduisent à la tractabilité, chacun avec son propre algorithme. 2-SAT forme l'une des six classes de Schaefer.

3. (Tractabilité hybride) Il existe également certaines classes d'instances qui n'entrent pas dans les deux autres catégories, mais qui peuvent être résolues en temps polynomial pour d'autres raisons.

   • Dániel Marx, Propriétés hypergraphiques tractables pour la satisfaction de contraintes et les requêtes conjonctives , STOC 2010. ( doi , preprint )
   • Thomas J. Schaefer, La complexité des problèmes de satisfiabilité , STOC 1978. ( doi )

Si vous comprenez l'algorithme de 2SAT, vous savez déjà pourquoi il est en P - c'est précisément ce que montre l'algorithme. Je pense que cette bande dessinée illustre mon propos. Comme vous savez déjà pourquoi 2SAT est dans P, vous voulez probablement savoir pourquoi 2SAT n'est pas NP-difficile.

Pour comprendre pourquoi 2SAT n’est pas un NP-difficile, vous devez considérer combien il est facile de réduire d’autres problèmes liés au NP. Pour comprendre intuitivement ceci, voyez comment réduire la SAT à 3SAT et essayez d'appliquer les mêmes techniques pour réduire la SAT à 2SAT. 2SAT n’est tout simplement pas aussi expressif que 3SAT et d’autres variantes de SAT.