Złożoność obliczania parzystości odczytu dwukrotnego przeciwnego do wzoru CNF (

W dwukrotnej, przeciwnej do odczytu formule CNF, każda zmienna pojawia się dwukrotnie, raz dodatnia, a raz ujemna.

Jestem zainteresowany w problem, który polega na obliczaniu parytetu liczby spełniających zadania o przeciwnej wzoru CNF odczytu dwukrotnie.$\oplus\text{Rtw-Opp-CNF}$

Nie udało mi się znaleźć odniesienia do złożoności takiego problemu. Najbliższe, jakie udało mi się znaleźć, to to, że licząca wersja jest # P -kompletna (patrz sekcja 6.3 w niniejszym dokumencie ).$\#\text{Rtw-Opp-CNF}$$\#\text{P}$

Z góry dziękuje za twoją pomoc.

Zaktualizuj 10 kwietnia 2016 r

• W tym artykule The problemu okazały się ⊕ P -Complete jednak formuła otrzymane drogą redukcji z 3 SAT nie jest CNF, i jak najszybciej starają się przekształcić go z powrotem do CNF dostaniesz wzór trzykrotnie.$\oplus\text{Rtw-Opp-SAT}$$\oplus\text{P}$$3\text{SAT}$
• Wersja monotoniczna jest pokazana jako ⊕ P -kompletna w tym dokumencie . W takim artykule ⊕ Rtw-Opp-CNF jest szybko wspomniany na końcu sekcji 4: Valiant mówi, że jest zdegenerowany. Nie jest dla mnie jasne, co dokładnie oznacza zdegenerowanie, ani co nie oznacza pod względem twardości.$\oplus\text{Rtw-Mon-CNF}$$\oplus\text{P}$$\oplus\text{Rtw-Opp-CNF}$

Zaktualizuj 12 kwietnia 2016 r

Byłoby również bardzo interesujące wiedzieć, czy ktokolwiek kiedykolwiek badał złożoność problemu . Biorąc pod uwagę dwukrotny odczyt CNF, taki problem wymaga obliczenia różnicy między liczbą zadowalających przypisań o nieparzystej liczbie zmiennych ustawionych na true a liczbą spełniających przypisań o parzystej liczbie zmiennych ustawionych na true. Nie znalazłem żadnej literatury na ten temat.$\Delta\text{Rtw-Opp-CNF}$

Zaktualizuj 29 maja 2016 r

Jak zauważył Emil Jeřábek w swoim komentarzu, nie jest prawdą, że Valiant powiedział, że problem jest zdegenerowany. Powiedział tylko, że bardziej ograniczona wersja takiego problemu, ⊕ Pl-Rtw-Opp-3CNF , jest zdegenerowana. Tymczasem nadal nie wiem, co dokładnie oznacza degeneracja, ale przynajmniej teraz wydaje się jasne, że jest to synonim braku ekspresyjnej mocy.$\oplus\text{Rtw-Opp-CNF}$$\oplus\text{Pl-Rtw-Opp-3CNF}$

Okazuje się, że każda formuła przeciwnego odczytu-dwukrotności ma parzystą liczbę satysfakcjonujących zadań. Oto niezły dowód, choć prawdopodobnie można by wyeliminować terminologię opartą na teorii grafów.

Niech będzie formułą CNF z odczytem przeciwnym do dwukrotnego odczytu. Bez utraty ogólności żadna klauzula nie zawiera zarówno zmiennej, jak i jej negacji.$\phi$

Rozważmy wykres którego zestaw wierzchołków jest klauzulami ϕ , a dla każdej zmiennej x dodajemy (nieukierowaną) krawędź, która występuje na dwóch klauzulach zawierających x . Nasze założenie WLOG w ϕ mówi, że ten wykres nie ma pętli własnych. Ponadto pomyśl o oznaczeniu każdej krawędzi zmienną ją definiującą; w ten sposób możemy rozróżnić równoległe krawędzie.$G$$\phi$$x$$x$$\phi$

Zorientowanie jest kierowany wykres której krawędzie utworzone są przez przypisanie do każdego kierunku krawędzi, G . Nazwij orientację G dopuszczalną, jeśli każdy wierzchołek G ma krawędź wychodzącą. Łatwo zauważyć, że spełniające zadania do cp są w bijective korespondencji z dopuszczalnych kierunków G .$G$$G$$G$ $G$$\phi$$G$

Teraz twierdzę, że liczba dopuszczalnych orientacji jest parzysta. Argumentem jest „inwolucja”: tworzę mapę Φ o następujących właściwościach:$G$$\Phi$

1. jest całkowicie zdefiniowany (każda dopuszczalna orientacja jest gdzieś odwzorowana)$\Phi$
2. wysyła dopuszczalne orientacje do dopuszczalnych orientacji$\Phi$
3. to inwolucja ( Φ ∘ Φ to tożsamość)$\Phi$$\Phi \circ \Phi$
4. nie ma stałych punktów$\Phi$

Raz są one ustalone, możemy zaobserwować, że orbity mieć wielkość 2 i podzielić dopuszczalnych orientacje G . Wynika z tego, że liczba dopuszczalnych orientacji jest parzysta.$\Phi$$G$

Aby zdefiniować , niech → G będzie dopuszczalną orientacją i rozważ złamanie → G w silnie połączonych komponentach. Sends następnie przesyła → G do orientacji utworzonej przez odwrócenie wszystkich krawędzi w silnie połączonych komponentach. Właściwości są następnie bezpośrednio sprawdzane:$\Phi$$\vec{G}$$\vec{G}$$\Phi$$\vec{G}$

1. Każdy ukierunkowany wykres można podzielić na ściśle powiązane komponenty.
2. Rozważ „DAG silnie połączonych komponentów” w ; nazwij to ilorazem. Zauważ, że Φ ( → G ) będzie mieć tę samą strukturę ilorazową, ponieważ Φ nie wpływa na krawędzie między SCC, a silnie połączone wykresy pozostają silnie połączone podczas odwracania wszystkich ich krawędzi. Ponadto, jeśli SCC ma więcej niż jeden wierzchołek, wówczas wszystkie jego wierzchołki składowe mają krawędź wejściową. Jeśli SCC ma tylko jeden wierzchołek i nie jest źródłem w ilorazie, wówczas wszystkie jego wierzchołki składowe mają krawędź wejściową. Aby pokazać Φ ( → G$\vec G$$\Phi(\vec G)$$\Phi$$\Phi(\vec G)$jest dopuszczalne, wystarczy wykazać, że SCC, które są źródłami w ilorazie, mają wiele wierzchołków. Wynika to jednak z faktu, że każdy wierzchołek komponentu ma krawędź wejściową, która musi pochodzić z innego wierzchołka komponentu, ponieważ nie ma pętli własnych, a komponent jest źródłem ilorazu.$G$
3. Wynika to z faktu, że iloraz struktura pokrywa się ze strukturą iloraz → G .$\Phi(\vec G)$$\vec G$
4. Dopuszczalność ma cykl, a zatem trochę SCC z krawędzią w środku.$\vec G$

Nie jestem pewien, czy mój pomysł jest zrozumiały, dlatego wyjaśnię na przykładzie Giorgio:

$( x_1 \lor x_2 \lor x_3 ) \land ( \lnot x_1 \lor \lnot x_3 \lor x_4 ) \land ( \lnot x_4 \lor x_5 ) \land ( \lnot x_2 \lor \lnot x_5 \lor \lnot x_6 )$

Najpierw muszę to zmienić w formularzu DNF:

$( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$

To powinno dać tę samą odpowiedź. I bez względu na to, czy obliczę liczbę rozwiązań modulo 2 w tym celu:

$( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$

lub w tym celu:

$( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$

Więc wybieram drugi. Mam implanty:

$i_0$$( x_1 \land x_2 \land x_3 )$

$i_1$$( \lnot x_1 \land \lnot x_3 \land x_4 )$

$i_2$$( \lnot x_4 \land x_5 )$

$i_3$$( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$

Teraz buduję układ równań:

${j_0}\oplus{j_1} = 1$

${j_0}\oplus{j_3} = 1$

${j_0}\oplus{j_1} = 1$

${j_2}\oplus{j_3} = 1$

${j_3} = 1$

$x_6$

$\oplus\text{Rtw-Opp-CNF}$${f(X)}\oplus{g(X)}$$f(X) \wedge g(X)$$f(X)$$g(X)$

$i_0\oplus{i_1}\oplus{i_2}\oplus{...}\oplus{i_{n-1}}$

$i_j$$x_0\wedge{x_1}\wedge{\neg{x_2}}$

$2^k$$i_0\oplus{i_1}\oplus{i_2}\oplus{...}\oplus{i_{n-1}}$

$i_0\vee{i_1}\vee{i_2}\vee{...}\vee{i_{n-1}}$

$a\vee{b} = a\oplus{b}\oplus({a\wedge{b}})$

1) ma wszystkie zmienne,

2) każda zmienna występuje dokładnie jedna (jeśli zmienna występuje dwa razy, to mamy jeden dodatni i ujemny w jednym implancie, więc da to wartość 0).

$x_0$$i_0$$x_0$$i_1$

${j_0}\oplus{j_1} = 1$

${j_0}$${j_1}$$i_0$$i_1$$i_0$$j_0$$j_0$$2^l$