Eigenschaften, die in 2-CNF oder 2-SAT ausgedrückt werden können

Wie zeigt man, dass eine bestimmte Eigenschaft nicht in 2-CNF (2-SAT) ausgedrückt werden kann? Gibt es irgendwelche Spiele, wie zum Beispiel Kieselspiele? Das klassische Schwarzkieselspiel und das Schwarz-Weißkieselspiel scheinen dafür ungeeignet zu sein (laut Hertel und Pitassi, SIAM J of Computing, 2010, sind sie PSPACE-vollständig).

Oder andere Techniken als Spiele?

Bearbeiten : Ich dachte an Eigenschaften, die das Zählen (oder die Kardinalität) eines unbekannten Prädikats beinhalten ( SO- Prädikat, wie Theoretiker endlicher Modelle sagen würden). Zum Beispiel wie in Clique oder ungewichtetes Matching. (a) Clique : Gibt es eine Clique in der gegebenen Grafik so dass eine bestimmte Anzahl ? (b) Matching : Gibt es ein passendes in so dass ?$C$$G$$|C| \ge$$K$$~$$M$$G$$|M| \ge K$

Kann 2-SAT zählen? Hat es einen Zählmechanismus? Scheint zweifelhaft.

Eine Familie von Bitvektoren ist die Klasse von Lösungen für ein 2-SAT-Problem, wenn und nur wenn sie die Median-Eigenschaft hat: Wenn Sie die bitweise Mehrheitsfunktion auf drei beliebige Lösungen anwenden, erhalten Sie eine andere Lösung. Siehe zB https://en.wikipedia.org/wiki/Median_graph#2-satisfiability und seine Referenzen. Wenn Sie also drei Lösungen finden, für die dies nicht zutrifft, wissen Sie, dass es nicht in 2-CNF ausgedrückt werden kann.

Sei eine Eigenschaft von n Variablen. Nehmen wir an, dass es eine 2CNF Formel φ ( x 1 , ... , x n , y 1 , ... , y m ) derart , dass P ( x 1 , ... , x n ) ⇔ ∃ y 1 ⋯ ∃ y m φ ( x $P(x_1,\ldots,x_n)$$n$$\varphi(x_1,\ldots,x_n,y_1,\ldots,y_m)$ Wir behaupten, dass φ einer 2CNF-Formel ψ mit nur x 1 , … , x n entspricht . Um dies zu beweisen, genügt es zu zeigen, wie man y m eliminiert. Schreib φ = & khgr; ∧ s ⋀ k = 1 ( y m ∨ U k ) ∧ t ⋀ l

$$P(x_1,\ldots,x_n) \Leftrightarrow \exists y_1 \cdots \exists y_m \varphi(x_1,\ldots,x_n,y_1,\ldots,y_m).$$ $\varphi$$\psi$$x_1,\ldots,x_n$$y_m$ wobeiUk,VℓLiterale sind undχymnicht mit einbezieht. Die Formelφist äquivalent zu χ∧( ¯ y m ⇒ s ⋀ k = 1 Uk)∧(ym⇒ t ⋀ ℓ = 1 Vℓ $$\varphi = \chi \land \bigwedge_{k=1}^s (y_m \lor U_k) \land \bigwedge_{\ell=1}^t (\overline{y_m} \lor V_\ell),$$ $U_k,V_\ell$$\chi$$y_m$$\varphi$ Dies beweist die Ansprüchewenn y m in einer Einheit Klausel nicht erscheint; Wenn dies der Fall ist, können wir es direkt beseitigen. $$\chi \land (\overline{y_m} \Rightarrow \bigwedge_{k=1}^s U_k) \land (y_m \Rightarrow \bigwedge_{\ell=1}^t V_\ell) \\ \Longleftrightarrow \\ \chi \land (\bigwedge_{k=1}^s U_k \lor \bigwedge_{\ell=1}^t V_\ell) \\ \Longleftrightarrow \\ \chi \land \bigwedge_{k=1}^s \bigwedge_{\ell=1}^t (U_k \lor V_\ell)$$ $y_m$

Wir schließen daraus, dass als 2CNF-Formel ausgedrückt werden kann, wenn es eine 2CNF-Formel ψ ( x 1 , … , x n ) gibt , die P entspricht . Daher kann eine Eigenschaft P als 2CNF ausgedrückt werden, wenn jede fälschende Zuweisung von höchstens zwei Literalen erzwungen wird. Insbesondere können K- Klasse und K- Übereinstimmung nicht als 2CNF ausgedrückt werden (mit Ausnahme des Eckfalles n- Klasse).$P(x_1,\ldots,x_n)$$\psi(x_1,\ldots,x_n)$$P$$P$$K$$K$$n$

$L$ $-$$L$

(Ja, ich kenne diese Additions-, Multiplikations- und Zählberechnungsfunktionen, aber es ist einfach, sie in Entscheidungsversionen ihrer jeweiligen Probleme umzuwandeln.)

$L \subseteq NL$$NL$$AC^0$$AC^0$

(c) , so zum Zählen , obwohl sie nicht in der Lage sein können , eine äquivalente Expression in 2-CNF, unter Verwendung des Verfahrens in (b) umrissenen zu erhalten, kann man eine erhalten equisatisfiable 2-CNF - Expression.

Also ja, 2-SAT kann zählen.

$NL$$|M|$$NL$