Was ist eine Zweiteilung? Ob 2-SAT selbst eine Dichotomie von SAT ist?

Kürzlich lese ich Artikel über Dichotomie . Ich verstehe nicht, welche Bedingung als Dichotomie bezeichnet werden kann ? Was bedeutet "eine Frage ist entweder in P oder in NP - vollständig "? (nehme P $\neq$ NP an )

Ich kenne zum Beispiel den Schäfer-Dichotomie-Satz, in dem eine Dichotomie darüber gegeben ist, ob eine Klasse von SAT in P ist. In diesem Theorem enthält die Dichotomie sechs Bedingungen, eine davon ist "2-SAT".

Meine Frage ist also, ob "2-SAT" selbst als Dichotomie oder triviale Dichotomie bezeichnet werden kann , weil 2-SAT in P ist, aber 3-SAT NP ist - vollständig ? In anderen Worten, frage ich mich , dass „wenn ein Sonderklasse eines NP - vollständiges Problem in ist P , dann ist diese Klasse eine Dichotomie ist oder eine triviale Dichotomie?“

Ein (grober) Dichotomiesatz besagt, dass in einer bestimmten Klasse von Problemen jedes Problem entweder in P oder NP-hart ist. Zum Beispiel betrifft Schäfers Dichotomiesatz die Klasse der Probleme der Form . Hier ist eine Sammlung von Booleschen Beziehungen, und ist das Problem der Entscheidung über die Erfüllbarkeit von Sätzen, die Konjunktionen von Beziehungen aus . Dies lässt sich am besten anhand eines Beispiels erklären. Das Problem 2SAT ist wobei aus den folgenden drei Prädikaten besteht: S S A T ( S ) S S A T ( S 2 ) S 2 ( x , y ) ↦ x ∨ y $\mathrm{SAT}(S)$$S$$\mathrm{SAT}(S)$$S$$\mathrm{SAT}(S_2)$$S_2$x , y S A T ( S H ) S H x ↦ x

$$(x,y) \mapsto x \lor y, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y.$$ Das heißt, jede Instanz von 2SAT ist eine Konjunktion von Klauseln einer dieser drei Formen, in denen Sie beliebige Variablen ersetzen können . Als ein weiteres Beispiel HORNSAT ist wo ist die folgende unendliche Sammlung: Schäfers Dichotomiesatz besagt, dass für jedes endliche$x,y$$\mathrm{SAT}(S_H)$$S_H$ $$\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*}$$ $S$ , das Problem liegt entweder in P oder es ist NP-vollständig (dies ist eine Dichotomie, da es nur zwei Möglichkeiten gibt). Zum Beispiel sind 2SAT und HORNSAT für jedes in P , während 3SAT NP-vollständig ist. Dies ist insofern überraschend, als wenn wir glauben, dass P NP, dann zeigt Ladners Theorem, dass es Zwischenprobleme gibt - Probleme, die weder in P noch in NP vollständig sind. Der Satz von Schaefer zeigt, dass diese Probleme nicht die Form .$\mathrm{SAT}(S)$$k$$k$$\neq$$\mathrm{SAT}(S)$

Eine verfeinerte Version von Schaefers Theorem besagt, dass entweder in co-NLOGTIME, L-vollständig, NL-vollständig, L-vollständig, P-vollständig oder NP-vollständig vorliegt . In den letzten Jahren wurden unzählige Verallgemeinerungen des Schaefer-Theorems bewiesen oder vermutet, darunter Ergebnisse zum Zählen von Lösungen und zur Annäherung an die maximale Anzahl erfüllbarer Klauseln sowie Ergebnisse über nicht-boolesche Domänen. Die Hauptvermutung ist die Feder-Vardi- Dichotomie-Vermutung, die besagt, dass Schäfers Theorem für Beziehungen auf beliebigen Domänen endlicher Größe gilt. Zum Status von Schaefers ursprünglichem Theorem für den Fall, dass unendlich ist, siehe diese Frage .$\mathrm{SAT}(S)$$\oplus$$S$

$\neq$$K_5$$K_{3,3}$

Beachten Sie, dass eine Dichotomie nicht das Ende der Geschichte ist und möglicherweise eine detailliertere Klassifizierung erstellt werden kann. Sie könnten ganz bei uns sein oder nur geringfügig gegen uns. Einige der polynomialen Fälle des Schaeffer-Theorems sind einfacher als andere (Allender, Bauland, Immerman, Schnoor, Voller, "Die Komplexität von Erfüllbarkeitsproblemen: Verfeinerung des Schaeffer-Theorems" . Journal of Computer and System Sciences , 75: 245-254, 2009.)