Qu'est-ce qu'une dichotomie? Si le 2-SAT lui-même est une dichotomie de SAT?

Récemment, je lis des articles sur la dichotomie . Je ne comprends pas quelle condition peut être qualifiée de dichotomie ? Que signifie «une question est soit en P soit en NP - complète »? (supposons P $\neq$ NP )

Par exemple, j'ai connu le théorème de dichotomie de Schaefer, dans lequel une dichotomie sur "si une classe de SAT est en P " est donnée. Dans ce théorème, la dichotomie contient six conditions, dont l'une est "2-SAT".

Donc ma question est, si "2-SAT" lui-même peut être appelé une dichotomie ou une dichotomie triviale , parce que 2-SAT est en P mais 3-SAT est NP - complet ? En d'autres termes, je me demande que "si une classe spéciale d'un problème NP - complet est en P , alors cette classe est une dichotomie? Ou une dichotomie triviale?"

Un théorème de dichotomie (grossier) indique que dans une certaine classe de problèmes, chaque problème est soit en P soit en NP-dur. Par exemple, le théorème de dichotomie de Schaefer concerne la classe de problèmes de la forme$\mathrm{SAT}(S)$. Ici$S$ est un ensemble de relations booléennes, et $\mathrm{SAT}(S)$ est le problème de décider de la satisfiabilité des propositions qui sont des conjonctions de relations $S$. Ceci est mieux expliqué par un exemple. Le problème 2SAT est$\mathrm{SAT}(S_2)$ avec $S_2$ composé des trois prédicats suivants:

$$(x,y) \mapsto x \lor y, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y.$$ Autrement dit, chaque instance de 2SAT est une conjonction de clauses de l'une de ces trois formes, où vous pouvez remplacer toutes les variables que vous souhaitez $x,y$. Comme autre exemple, HORNSAT est$\mathrm{SAT}(S_H)$ où $S_H$ est la collection infinie suivante: $$\begin{gather*} x \mapsto x, \quad x \mapsto \lnot x, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y, \\ (x,y,z) \mapsto x \lor \lnot y \lor \lnot z, \quad (x,y,z) \mapsto \lnot x \lor \lnot y \lor \lnot z, \\ (x,y,z,w) \mapsto x \lor \lnot y \lor \lnot z \lor \lnot w, \quad (x,y,z,w) \mapsto \lnot x \lor \lnot y \lor \lnot z \lor \lnot w, \ldots \end{gather*}$$ Le théorème de dichotomie de Schaefer indique que pour chaque fini $S$, le problème $\mathrm{SAT}(S)$est soit en P soit NP-complet (c'est une dichotomie car il n'y a que deux possibilités). Par exemple, 2SAT et$k$-HORNSAT sont en P pour chaque $k$, tandis que 3SAT est NP-complete. Cela est surprenant car si nous pensons que P$\neq$NP alors le théorème de Ladner montre qu'il y a des problèmes intermédiaires - des problèmes qui ne sont ni en P ni NP-complets. Le théorème de Schaefer montre que ces problèmes ne peuvent pas être de la forme$\mathrm{SAT}(S)$.

Une version plus raffinée du théorème de Schaefer déclare que $\mathrm{SAT}(S)$ est soit en co-NLOGTIME, L-complet, NL-complet, $\oplus$L-complet, P-complet ou NP-complet. Au cours des dernières années, d'innombrables généralisations du théorème de Schaefer ont été prouvées ou conjecturées, y compris des résultats sur les solutions de comptage et l'approximation du nombre maximum de clauses satisfaisables, ainsi que des résultats sur des domaines non booléens. La conjecture principale est la conjecture de dichotomie de Feder-Vardi qui stipule que le théorème de Schaefer est valable pour les relations sur des domaines arbitraires de taille finie. Pour le statut du théorème original de Schaefer dans le cas où$S$est infini, voir cette question .

Le mot «dichotomie» vient de la dichotomie grecque signifiant divisé, ou divisé en deux. Ainsi, une dichotomie est une déclaration de la forme, "Tout est soit A ou B mais pas les deux." L'exemple classique est: «Vous êtes avec nous ou contre nous». La dichotomie de Schaeffer pour le CSP booléen (qu'il appelle "Satisfaction généralisée") est un autre exemple: pour chaque ensemble fini de relations booléennes, le problème de satisfiabilité correspondant est soit en P soit en NP-complet (mais pas les deux, en supposant que P$\neq$NP). Le théorème de Kuratowski est aussi une dichotomie: chaque graphe est soit plan de contient$K_5$ ou $K_{3,3}$ en tant que mineur (topologique).

Notez qu'une dichotomie n'est pas la fin de l'histoire et il pourrait être possible de produire une classification plus détaillée. Vous pourriez être complètement avec nous ou seulement légèrement contre nous. Certains des cas polynomiaux du théorème de Schaeffer sont plus faciles que d'autres (Allender, Bauland, Immerman, Schnoor, Voller, "The Complexity of Satisfiability Problems: Refining Schaeffer's Theorem" . Journal of Computer and System Sciences , 75: 245-254, 2009.)