Jakie są podrodziny # P-complete z # 2-SAT?

Krótka wersja.

Oryginalny dowód, że # 2-SAT jest #P- kompletny, pokazuje w rzeczywistości, że te przypadki # 2-SAT, które są zarówno monotoniczne (nie obejmujące negacji żadnych zmiennych), jak i dwustronne (wykres utworzony przez klauzule nad zmienne to wykres dwustronny) są # P-twarde . Zatem dwa specjalne przypadki # 2-MONOTONE-SAT i # 2-BIPARTITE-SAT to #P- twarde . Czy istnieją inne szczególne przypadki, które można scharakteryzować pod względem „naturalnych” właściwości formuły, które są również twarde #P ?

Długa wersja.

Problem nr 2-SAT polega na obliczeniu - dla wzoru logicznego składającego się z połączenia kilku klauzul, gdzie każda klauzula jest rozłączeniem dwóch literałów x j lub ˉ x j - liczby łańcuchów logicznych x ∈ { 0 , 1 } n takie, że ϕ ( x ) = 1 . Ustalenie, czy istnieje taki x, jest łatwe; ale zliczanie ogólnej liczby rozwiązań jest zakończone #P , jak pokazuje Valiant w$\phi$$x_j$$\bar x_j$$x \in \{0,1\}^n$$\phi(x) = 1$$x$Złożoność problemów z wyliczaniem i niezawodnością, SIAM J. Comput., 8 , s. 410–421 .

W szczególności w przypadku # 2-SAT, Valiant faktycznie pokazuje redukcję do # 2-SAT z liczenia dopasowań (w tym niedoskonałych) na grafach dwustronnych, co daje początek przypadkom # 2-SAT o bardzo szczególnej strukturze , jak następuje.

1. Po pierwsze należy zauważyć, że problem monotoniczne odpowiada poprzez podstawienie problemu, w którym dla każdej zmiennej , albo x j występuje we wzorze cp lub °° x j czyni ale nie jednocześnie. W szczególności problem „zmniejszania monotonicznego”, w którym występują tylko negacje ˉ x j dla każdej zmiennej, jest dokładnie tak samo trudny jak przypadek monotoniczny.$x_j$$x_j$$\phi$$\bar x_j$$\bar x_j$

2. Dla każdego wykresu o m krawędziach możemy zbudować wzór 2-SAT zmniejszający monotonię odpowiadający dopasowaniom - kolekcje krawędzi, które nie mają żadnych wierzchołków - poprzez przypisanie zmiennej x e do każdej krawędzi, reprezentującej czy jest zawarty w zestawie krawędzi; właściwość zbioru M ⊆ E będącego dopasowaniem jest równoważna wektorowi padania x = χ M spełniającemu wzór CNF ϕ, którego zdania są podane przez ( ˉ x e ∨ ˉ x f$G = (V,E)$$m$$x_e$$M \subseteq E$$\mathbf x = \chi_M$$\phi$$(\bar x_e \vee \bar x_f)$ dla każdej pary krawędzi które dzielą wierzchołek. Z założenia$e, f \in E$ ma wiele Zadowalające rozwiązania x ∈ { 0 , 1 } m , ponieważ nie są (ewentualnie niedoskonały) skojarzeń na wykresie G .$\phi$$\mathbf x \in \{0,1\}^m$$G$

3. Jeśli wykres dla którego chcemy policzyć dopasowania, jest dwustronny, to nie zawiera żadnych cykli nieparzystych - które możemy opisać jako sekwencję krawędzi na wykresie, która zaczyna się i kończy tą samą krawędzią (bez podwójnego liczenia tej krawędzi końcowej) . Wtedy nie ma sekwencji zmiennych x e , x f , x g , … , x e o nieparzystej długości w ϕ , w których sąsiednie zmienne są zawarte we wspólnej klauzuli. Wtedy wzór ϕ byłby dwustronny w sposób opisany wcześniej.$G$$x_e, x_f, x_g, \ldots, x_e$$\phi$$\phi$

4. Zliczanie liczby skojarzeń w dowolnej dwudzielnych wykresów, w szczególności, może być wykorzystywany do zliczania liczby doskonałych skojarzeń z dwustronnym wykresu: podany wejście bitrarite wykres z dwoma bipartitions A , B, z sam rozmiar n , można utworzyć wykresy G K przez zwiększanie A z gdziekolwiek 0 ⩽ k ⩽ n dodatkowych wierzchołków połączona z wszystkimi wierzchołkami B . Ponieważ wszystkie dopasowania w $G = (A \cup B, E)$$A, B$$n$$G_k$$A$$0 \leqslant k \leqslant n$$B$$G$o danym rozmiarze w inny sposób przyczyniają się do ilości skojarzeń z , poprzez zliczanie tych można określić liczbę skojarzeń z G o rozmiarze n (to znaczy są doskonałymi skojarzeń); i zauważ, że zliczanie liczby idealnych dopasowań na wykresach dwustronnych jest równoważne obliczaniu stałych { 0 , 1 } -matryce za pomocą prostej korespondencji.$G_k$$G$$n$$\{0,1\}$

Klasą instancji # 2-SAT, które są pokazane jako #P- twarde, są wówczas monotoniczne dwustronne instancje.

Pytanie: Jakie są inne szczególne przypadki # 2-SAT, które są #P- zakończone , w wyniku tego lub innej redukcji?

Byłoby interesujące, gdyby oprócz pokazywania / powoływania się na redukcję, ludzie mogliby również opisać intuicyjny powód, dla którego szczególny przypadek może stanowić przeszkodę w naturalnym podejściu do liczenia zadań satyfikujących. Na przykład, chociaż MONOTONE-2-SAT jest trywialnie rozwiązywalny ( jest zawsze rozwiązaniem), instancje monotoniczne to takie, w których przypisanie pewnej zmiennej do stałej wartości rutynowo nie nałoży wielu ograniczeń na pozostałe zmienne. Naprawienie dowolnej zmiennej x j = 0 ogranicza tylko wartości zmiennych bezpośrednio z nią związanych przez jakąś klauzulę; i ustawienie x j = $\mathbf x = 1^n$$x_j = 0$$x_j = 1$nie ogranicza w ogóle możliwych wartości żadnych innych zmiennych. (Nie jest jednak jasne, czy porównywalne ograniczenie do grafów dwustronnych jest znaczące w ten sam sposób; ograniczenie dwustronne wydaje się raczej dodawać strukturę niż ją usuwać, ale nie dodaje struktury wystarczającej do skutecznego liczenia).

Edytowano, aby dodać. Punkty bonusowe zostaną przyznane za każdą taką klasę, która ostatecznie nie opiera się na istnieniu monotonicznych instancji (jak powyżej # 2-BIPARTITE-SAT, których twardość jest najwyraźniej spowodowana włączeniem specjalnego przypadku #P -hard # 2 -MONOTONE-BIPARTITE-SAT). Na przykład interesujący byłby argument dotyczący twardości # 2-BIPARTITE-SAT, który nie opiera się na instancjach monotonicznych (ale może opierać się na jakiejś innej podrodzinie).

# 3-Regularna dwustronna dwustronna pokrywa wierzchołków jest # P-Complete

Ponieważ liczenie okładek wierzchołków jest dokładnie takie samo, jak liczenie spełniających się zadań monotonicznych instancji # 2-SAT, powyższy wynik sugeruje, że liczenie spełniających przypisań instancji nr 2-SAT, która jest monotoniczna i 3-regularna, jest zakończone i dwustronny i płaski .

To z kolei oznacza, że ​​oprócz dwóch przypadków specjalnych # 2-MONOTONE-SAT i # 2-BIPARTITE-SAT, o których już wspomniano w pytaniu, dwa przypadki specjalne # 2-CUBIC-SAT i # 2-PLANAR-SAT to # P-complete również.