O Inverse 3-SAT

Kontekst : Kavvadias i Sideri wykazali, że odwrotny problem 3-SAT jest coNP zakończony: Biorąc pod uwagę $\phi$ zestaw modeli $n$ zmiennych, czy istnieje wzór 3-CNF taki, że $\phi$ jest jego dokładnym zestawem modeli? Powstaje formuła bezpośredniego kandydata, która jest połączeniem wszystkich 3-klauzul spełnionych przez wszystkie modele w $\phi$ .

Ponieważ zawiera wszystkie 3-klauzule, które implikuje, tę formułę kandydującą można łatwo przekształcić w równoważną formułę $F_{\phi}$ która jest 3-zamknięta w ramach rozdzielczości - 3-zamknięcie wzoru jest podzbiorem jego zamknięcia w rozdzielczości zawierającej tylko klauzule rozmiar 3 lub mniejszy. Formuła CNF jest zamykana w ramach rozstrzygania, jeśli wszystkie możliwe rozpuszczalniki są uwzględnione przez klauzulę wzoru - klauzula $c_1$ jest objęta klauzulą $c_2$ jeśli wszystkie literały $c_2$ są w $c_1$ .

Biorąc pod uwagę $I$ , częściowe przypisanie zmiennych tak, że nie $I$ podzbiorem żadnego modelu $\phi$ .

Zadzwoń do indukowane wzór przez naniesienie I do F φ : Każdy punkt, który zawiera dosłownym rozpoznawaną t r u e pod I jest usunięta z preparatu i wszelkich literałach które oceniają do f danego ł s e pod I są usuwane z klauzul .$F_{\phi|I}$$I$$F_{\phi}$$true$$I$$false$$I$

Zadzwoń do , wzór wyprowadzony z F ϕ | Mam wszystkie możliwe 3 ograniczone rozdzielczości (w których rezolwent i operandy mają co najwyżej 3 literały) i podsumowania.$G_{\phi|I}$$F_{\phi|I}$

Pytanie : Czy $G_{\phi|I}$ 3-zamknięte na podstawie uchwały?

Odpowiedź: Tak (nawet jeśli podzbiorem jakiegoś modelu ϕ )$I$$\phi$

Niech zestaw klauzul, które wywodzą się z F ϕ ∪ F ϕ | I przez wszystkie możliwe 3-ograniczone uchwały i przypuszczenia ( R | I to 3-ograniczone zamknięcie F ϕ ∪ F ϕ | I ). Biorąc C klauzuli obserwowaną F cp , to istnieją co najmniej jednej podgrupie R | Ja, których klauzule sugerują c . Nazwa R c taki podzbioru.$R_{|I}$$F_{\phi} \cup F_{\phi|I}$$R_{|I}$$F_{\phi}\cup F_{\phi|I}$$c$$F_{\phi}$$R_{|I}$$c$$R_c$

Niech następującą właściwość: Dla wszystkich c implikowanych przez F ϕ takich, że | c | Ja | ≤ 3 ,$P(k)$$c$$F_{\phi}$$|c_{|I}| \le 3$

taki, że | R c | ≤ k ⇒ c | I jest podporządkowana jakimś punkcie ∈ G cp | Ja$[\exists R_c \subseteq R_{|I}$$|R_c|\le k \Rightarrow c_{|I}$$\in G_{\phi|I}]$

Tutaj zaczyna się nawrót. Biorąc pod uwagę implikowane przez F ϕ takie, że | c | Ja | ≤ 3 , tj. C | I ∈ 3-zamknięcie F cp | Ja .$c$$F_{\phi}$$|c_{|I}|\le 3$$c_{|I} \in$$F_{\phi|I}$

1. . Jeśli ∃ R c ⊆ R | I / | R c | = 1, a następnie R c = { d } ( d ∈ F ϕ ∪ F ϕ | I przyjmuje c ) ic | I jest uwzględniana przez d | I ∈ F ϕ | I (zauważ, że każda klauzula F ϕ |$k=1$$\exists R_c \subseteq R_{|I} / |R_c|=1$$R_c=\{d\}$$d \in F_{\phi}\cup F_{\phi|I}$$c$$c_{|I}$$d_{|I} \in F_{\phi|I}$$F_{\phi|I}$jest objęty jakąś klauzulą ). Zatem P ( 1 ) .$G_{\phi|I}$$P(1)$

2. Załóżmy, że dla k ≥ 1 . Jeśli ∃ R c ⊆ R | Ja taki, że | R c | ≤ k + 1 (a nie inny R C o rozmiarze 1 tak, C ∉ F φ i | c | > 3 ), a następnie Załóżmy, C = ( α β y L I ) gdzie α , β $P(k)$$k\ge1$$\exists R_{c}\subseteq R_{|I}$$|R_{c}|\le k+1$$R_{c}$$c\notin F_{\phi}$$|c|>3$$c=(\alpha \beta \gamma L_{I})$ są literałami nie ustawionymi przez I, a L I jest podzbiorem literałów, których wszystkie wartości wynoszą 0 pod I ( L I ≠ ∅ ) , tj. c | I = ( α β γ ) , przy czym α , β , γ niekoniecznie są różne. $\alpha ,\beta ,\gamma$$I$$L_{I}$$I (L_I \neq \varnothing)$$c_{|I}=(\alpha \beta \gamma)$$\alpha ,\beta ,\gamma$

3. Usuń klauzulę z R c, tak aby | d i | Ja | < | d i | ≤ 3 , innymi słowy, taki, że d i zawiera literał z L I (istnieje co najmniej jedna taka klauzula w R c od L I ≠ ∅ ) i | d i | Ja | ≤ 2 .$d_{i}$$R_{c}$$|d_{i|I}|<|d_{i}|\le3$$d_{i}$$L_{I}$$R_{c}$$L_I \neq \varnothing$$|d_{i|I}|\leq 2$

4. Rozmiar pozostałego zestawu wynosi ≤ k . Jeżeli pewna klauzula c ′ = ( α β γ L ′ I ) jest implikowana przez R c ∖ d i (gdzie L ′ I jest podzbiorem literałów, wszystkie mają wartość 0 pod I ), to | c ′ | Ja | = 3 i ∃ R c ′ = R c ∖ $R_{c}\setminus d_{i}$$\le k$$c'=(\alpha \beta \gamma L'_{I})$$R_{c}\setminus d_{i}$$L'_{I}$$I$$|c'_{|I}|=3$ taki, że | R c ′ | ≤k. WedługP(k), c ′ | I =(αβγ)jest następnie uwzględnione przez jakąś klauzulę∈ G ϕ | I , indukującP(k+1)dlac.$\exists R_{c'}=R_{c}\setminus d_{i}\subseteq R_{|I}$$|R_{c'}|\le k$$P(k)$$c'_{|I}=(\alpha \beta \gamma)$$\in G_{\phi|I}$$P(k+1)$$c$

5. Jeśli zawiera ˉ α lub ˉ β lub ˉ γ, a następnie d i | Nie ma sensu sugerować, że [niektóre klauzule zawierają] c . Zatem R c ∖ d i implikuje c , indukując P ( k + 1 ), jak pokazano wcześniej.$d_{i|I}$$\bar \alpha$$\bar \beta$$\bar \gamma$$d_{i|I}$$c$$R_{c}\setminus d_{i}$$c$$P(k+1)$

6. Jeśli podsumowuje c | I wtedy P ( k + 1 ) jest spełnione dla c .$d_{i|I}\in F_{\phi|I}$$c_{|I}$$P(k+1)$$c$

7. Jeśli wchodzę w c | I i nie zawiera ˂ alfa lub ˉ beta lub ˉ y wówczas d : i | I = ( x ) lub d i | I = ( a x ) lub d i | I = ( x y ) , gdzie x i y ∉ { α β $d_{i|I}$$c_{|I}$$\bar \alpha$$\bar \beta$$\bar \gamma$$d_{i|I}=(x)$$d_{i|I}=(ax)$$d_{i|I}=(xy)$$x$$y$ I nie są przez I i ∈ { a- beta y } .$\notin\{\alpha \beta \gamma \}$$I$$a \in\{\alpha \beta \gamma \}$

   • Jeśli a następnie R c ∖ d i implikuje ( ˉ x α β γ L I ) (przypomnijmy, że sugerowanie pewnej klauzuli C oznacza sugerowanie klauzuli obejmującej C ). Ponieważ dowolna rozdzielczość z d i | I = ( x ), ponieważ operand usuwa ˉ x z drugiego operandu, a następnie nie ma klauzuli R c ∖ d $d_{i|I}=(x)$$R_{c}\setminus d_{i}$$(\bar{x}\alpha \beta \gamma L_{I})$$C$$C$$d_{i|I}=(x)$$\bar{x}$$R_{c}\setminus d_{i}$zawiera (ponieważ R c ∖ d i ⊆ R | I, co stanowi 3-ograniczone zamknięcie F ϕ ∪ F ϕ | I ). Następnie R c ∖ d I oznacza ( a- beta y L I ) , powodując P ( k + 1 ) , jak pokazano w punkcie (4).$\bar x$$R_{c}\setminus d_{i} \subseteq R_{|I}$$F_{\phi}\cup F_{\phi|I}$$R_{c}\setminus d_{i}$$(\alpha \beta \gamma L_{I})$$P(k+1)$

   • Jeśli a następnie R c ∖ d i implikuje ( ˉ x α β γ L I ) . Wymienić ˉ x przez w każdej możliwej klauzuli R c ∖ d i (jeżeli nowy punkt jest uwzględniana po pewnym klauzuli R | I , należy klauzuli podporządkowania zamiast mimo klauzula zastępując w. R | I ). Nazwa R $d_{i|I}=(ax)$$R_{c}\setminus d_{i}$$(\bar{x}\alpha \beta \gamma L_{I})$$\bar{x}$$a$$R_{c}\setminus d_{i}$$R_{|I}$$R_{|I}$ wynikowy zbiór ( R c , d i ⊆ R | I ). Następnie R c , d I oznacza(a-betay L I ), powodującP(k+1),jak opisano powyżej.$R_{c,d_{i}}$$R_{c,d_{i}}\subseteq R_{|I}$$R_{c,d_{i}}$$(\alpha \beta \gamma L_{I})$$P(k+1)$

   • Jeśli a następnie R c ∖ d i implikuje ( ˉ x α β γ L I ) i ( ˉ y α β γ L I ) . Zamień ˉ x na y w każdej możliwej klauzuli R c ∖ d i (jak wyżej, jeśli nowa klauzula jest zastąpiona przez jakąś klauzulę w R |$d_{i|I}=(xy)$$R_{c}\setminus d_{i}$$(\bar{x}\alpha \beta \gamma L_{I})$$(\bar{y}\alpha \beta \gamma L_{I})$$\bar{x}$$y$$R_{c}\setminus d_{i}$$R_{|I}$, zamiast tego zachowaj klauzulę sumowania). Nazwa wynikowy zestaw ( R c , d i ⊆ R | I ). Następnie R c , d I oznacza ( Y a- beta y L I ) . Ponieważ implikuje również ( ˉ y α β γ L I ), to implikuje rezolwent ( α β γ L I ) , indukując $R_{c,d_{i}}$$R_{c,d_{i}}\subseteq R_{|I}$$R_{c,d_{i}}$$({y}\alpha \beta \gamma L_{I})$$(\bar{y}\alpha \beta \gamma L_{I})$$(\alpha \beta \gamma L_{I})$ .$P(k+1)$

Przez to ponowne wystąpienie każda klauzula 3-zamknięcie F ϕ | I jest podporządkowana jakimś punkcie ∈ G cp | Ja (również w drugą stronę). Następnie G ϕ | I odpowiada 3-zamknięcia F cp | Ja .$\in$$F_{\phi |I}$$\in G_{\phi|I}$$G_{\phi|I}$$F_{\phi |I}$

Nie rozumiem, w jaki sposób można obliczyć w czasie wielomianowym, ponieważ samo wykonanie rozdzielczości zajmuje czas wykładniczy (w najgorszym przypadku). Na przykład, powiedzmy, że twoja kandydująca formuła 3-CNF F 1 jest następująca: F 1 : = { { a , b , c } , { d , e , ¬ c } , { a , ¬ b , f } , { d , e , ¬ f } $F_\phi$$F_1$

$F_\phi$