Tłumaczenie SAT z HornSAT

26

Czy można przetłumaczyć wzór B logiczny na równoważną kombinację klauzul Horna? Artykuł w Wikipedii na temat HornSAT wydaje się sugerować, że tak, ale nie byłem w stanie ścigać żadnego odniesienia.

Zauważ, że nie mam na myśli „w czasie wielomianowym”, ale raczej „w ogóle”.

reference-request lo.logic sat

— Evgenij Thorstensen
źródło

1

Co rozumiesz przez „tłumaczyć”? Oczywiste jest, że istnieją instancje SAT, których nie można zapisać jako formułę HornSAT. Na przykład klauzula (p lub q). Ale może masz na myśli, że chcesz takiej redukcji, aby wejściowa formuła SAT była zadowalająca i czy wyjściowa formuła HornSAT jest zadowalająca? W takim przypadku oczywiście jest trywialna redukcja, ponieważ nie zależy ci na wydajności ...

— arnab

Nie mam na myśli równości, ponieważ jest to trywialne bez ograniczeń wydajności. Mam na myśli równoważne jak w „mają takie same zadowalające przypisania”, gdy rozważamy zmienne wspólne zarówno dla instancji SAT, jak i odpowiedniej instancji HornSAT (jeśli musieliśmy dodać jakieś zmienne pomocnicze, to je rzutujemy). Zgadzam się, że nie powinno to być możliwe, dokładnie na przykład (P przeciwko Q), ale nie wiem, jak to udowodnić. Czy masz na myśli szkic próbny?

— Evgenij Thorstensen

3

Pytanie jest nadal niejednoznaczne. Czy potrafisz wyjaśnić, co rozumiesz przez „rzutowanie ich”? Czy masz na myśli „przypisanie A spełnia instancję SAT F, jeżeli istnieje przypisanie B do zmiennych pomocniczych, tak że (A, B) spełnia wystąpienie HornSAT F”? Jeśli tak, to myślę, że możesz to zrobić po prostu używając kompletności P HornSAT.

— Ryan Williams,

24

Nie. Klauzule Rogu dopuszczają najmniej modeli Herbranda, których nie mają rozróżnienia literałów pozytywnych. Por. Lloyd, 1987, Foundations of Logic Programming .

Najmniejsze modele Herbrand mają tę właściwość, że znajdują się na skrzyżowaniu wszystkich satysfakcji. Modelami Herbrand dla są , który nie zawiera jego przecięcia, tak jak mówi arnab, jest przykładem wzoru, którego nie można wyrazić jako koniunkcję klauzul Horn. $(a \lor b)$ $\{\{a\}, \{b\}, \{a,b\}\}$ $(a \lor b)$

Niepoprawna odpowiedź nadpisana

— Charles Stewart
źródło

Sprytne, ale klauzula -a_1 & ... & -a_n -> # nie jest klauzulą Horn.

— Evgenij Thorstensen

@Evgenij: Jest.

— Radu GRIGore

4

Klauzula rogowa to rozbieżność literałów z co najwyżej jednym literałem dodatnim. Przekładając powyższe na rozbieżność literałów, otrzymujemy a_1 v ... v a_n, przy czym wszystkie literały są pozytywne. Powyższa klauzula ma podwójny róg, ale to nie pomaga mojemu zainteresowaniu.

— Evgenij Thorstensen

@rgrig: Nie, byłem zmieszany. @Evgenij: Odpowiedź naprawiona.

— Charles Stewart,

5

Zgodność można osiągnąć w następujący sposób (redukcja z 2SAT do HornSAT). W ten sposób można również zredukować do formuły Horn. Dzięki Joshua Gorchow za zwrócenie uwagi na tę redukcję. $(p \lor q)$

Dane wejściowe: wzór 2-SAT z klauzulami , ..., na zmiennych , ..., . $\phi$ $C_1$ $C_k$ $x_1$ $x_n$

Skonstruuj formułę Horn w następujący sposób: $Q$

Nie będzie 4 ( wybrać ) nowych zmiennych, po jednym dla każdej możliwej ewentualnej 2-cnf klauzuli o zmiennych o co najwyżej 2 literałów ( nie tylko te klauzul ) - jest to łącznie z klauzulami jednostkowymi i pustymi. Nowa zmienna odpowiadająca klauzuli będzie oznaczona przez . $\times$ $n$ $2$ $+ 2n + 1$ $x$ $C_i$ $\phi$ $D$ $z_D$

4 ( wybierz ) wynika z faktu, że każda para daje początek 4 klauzulom 2-cnf. wynika z faktu, że każdy może utworzyć 2 klauzule jednostkowych. I w końcu „jeden” pochodzi z pustej klauzuli. Zatem całkowita liczba możliwych klauzul 2-cnf wynosi 4 ( wybierz ) . $\times$ $n$ $2$ $(x_i, ~x_j)$ $2n$ $x_i$ $=$ $\times$ $n$ $2$ $+ 2n + 1$

Jeśli klauzula 2-cnf wynika z dwóch innych klauzul 2-cnf i jednym krokiem rozdzielczości, to dodajemy klauzulę Horn do ... Ponownie, robimy to dla Wszystkie ewentualne 2-CNF klauzule - wszystkie 4 ( wybrać ) z nich - nie tylko . $F$ $D$ $E$ $(z_D \land z_E \to z_F)$ $Q$ $\times$ $n$ $2$ $+2n+1$ $C_i$

Następnie dodajemy klauzul jednostka do , dla każdej klauzuli występującego na wejściu ... Na koniec dodamy klauzulę jednostkową do . $z_{C_i}$ $Q$ $C_i$ $\phi$ $(\neg z_{empty})$ $Q$

Formuła klaksonu jest teraz ukończona. Zauważ, że zmienne użyte w są całkowicie różne od zmiennych używanych w . $Q$ $Q$ $\phi$

— Martin Seymour
źródło

Czy ktoś zna algorytm w innym kierunku? Biorąc pod uwagę formułę Horn , czy istnieje metoda uzyskania równoważnego wyrażenia 2SAT (2CNF) , tak aby było satysfakcjonujące tylko wtedy, gdy jest? Używasz tego samego zestawu zmiennych lub używasz dodatkowych zmiennych, albo używasz zupełnie innego zestawu zmiennych (jak w powyższej odpowiedzi)? Czy dowód, że jest to niemożliwe?

ϕ_{1}

$\phi_1$

ϕ_{2}

$\phi_2$

ϕ_{1}

$\phi_1$

ϕ_{2}

$\phi_2$

— Martin Seymour

2

Nie sądzę, żeby to było możliwe. Na przykład nie ma sposobu, aby napisać jako połączenie klauzul tubowych, ponieważ zakazuje tylko pojedynczego przypisania prawdy, a mianowicie 0011. Każda klauzula tubowa z mniej niż 4 literałami zakazałoby więcej niż 1 przypisania prawdy, a klauzule rogowe z 4 literałami mogą zakazać przypisania prawdy tylko z jednym 0. $\phi = (X_1 \vee X_2 \vee \neg X_3 \vee \neg X_4)$ $\phi$

Edycja: oops nie zauważył, że na to już odpowiedziano