Eine 3-CNF-Formel, die die Auflösungsbreite

Es sei daran erinnert, dass die Breite einer Auflösungs-Widerlegung einer CNF-Formel die maximale Anzahl von Literalen in einer Klausel ist, die in . Für jedes gibt es nicht erfüllbare Formeln in 3-CNF. Jede Auflösungs-Widerlegung von erfordert eine Breite von mindestens .$R$$F$$R$$w$$F$$F$$w$

Ich brauche ein konkretes Beispiel für eine unbefriedigende Formel in 3-CNF (so klein und einfach wie möglich), die keine Auflösungs-Widerlegung der Breite 4 hat.

Das folgende Beispiel stammt aus dem Artikel, der eine kombinatorische Charakterisierung der Auflösungsbreite durch Atserias und Dalmau liefert ( Journal , ECCC , Autorenexemplar ).

Theorem 2 der Arbeit besagt, dass unter der Annahme einer CNF-Formel Auflösungs-Widerlegungen mit einer Breite von höchstens k für F Gewinnstrategien für Spoiler im existentiellen ( k + 1 ) -Kieselspiel entsprechen. Denken Sie daran, dass das existenzielle Pebble-Spiel zwischen zwei konkurrierenden Spielern, genannt Spoiler und Duplicator, gespielt wird und die Positionen des Spiels partielle Zuweisungen der Domänengröße von höchstens k + 1 zu Variablen von F sind . Im ( k + 1 ) -Kieselspiel will Spoiler ausgehend von der leeren Aufgabe eine Klausel von F fälschen$F$$k$$F$$(k+1)$$k+1$$F$$(k+1)$$F$Dabei werden höchstens boolesche Werte gleichzeitig gespeichert, und Duplicator möchte verhindern, dass Spoiler dies tut.$k+1$

Das Beispiel basiert auf (der Negation von) dem Pigeonhole-Prinzip.

Für jedes und j ∈ { 1 , … , n } sei p i , j eine aussagekräftige Variable, was bedeutet, dass die Taube i in Loch j sitzt . Für jedes i ∈ { 1 , … , n + 1 } und j ∈ { 0 , … , n } sei$i \in \{1, \dotsc, n+1 \}$$j \in \{1, \dotsc, n \}$$p_{i,j}$$i$$j$$i \in \{1, \dotsc, n+1 \}$$j \in \{0, \dotsc, n \}$ sei eine neue Satzvariable. Die folgende 3 -cnf Formel E P i zum Ausdruckdass Taube i in irgendeinem Loch sitzt: E P i ≡ ¬ y i , 0 ∧ n ⋀ j = 1 ( y i , j - 1 ∨ p i , j ∨ ¬ y i , j ) ∧ y i , n$y_{i,j}$$3$${EP}_i$$i$

$${EP}_i \equiv \neg y_{i,0} \wedge \bigwedge_{j=1}^n (y_{i,j-1} \vee p_{i,j} \vee \neg y_{i,j} ) \wedge y_{i,n}.$$ Schließlich ist die -cnf Formel E P H P n + 1 n die Negation des pigeonhole Prinzip exprimierenden ist die Konjunktion aller E P i und alle Klauseln H i , j k ≡ ¬ p i , k ∨ ¬ p j , k für i , j ∈ { 1 , … , n + 1 } , i ≠ j und$3$${EPHP}_n^{n+1}$${EP}_i$$H_k^{i,j} \equiv \neg p_{i,k} \vee \neg p_{j,k}$$i,j \in \{1, \dotsc, n+1 \}, i \ne j$ .$k \in \{1, \dotsc, n \}$

Lemma 6 des Papiers gibt einen ziemlich kurzen und intuitiven Beweis dafür , dass Spoiler nicht gewinnen können -Kieselstrand Spiel auf E P H P n + 1 n , also E P H P n + 1 n hat keine Resolutionswiderlegung der Breite höchstens n - 1 .$n$${EPHP}_n^{n+1}$${EPHP}_n^{n+1}$$n-1$

Die Arbeit hat ein weiteres Beispiel in Lemma 9, das auf dem Prinzip der dichten linearen Ordnung basiert.

$\Omega(n^{(k-3)/12})$$k+1$