Jądro wielomianowe dla FLIP SAT na formułach -CNF

Problem parametryzowany przez k-FLIP SAT definiuje się jako:

Dane wejściowe: formuła 3-CNF z zmiennymi i przypisaniem prawdy \ sigma: [n] \ to \ {0,1 \} Parametr: k Pytanie: czy możemy przekształcić przypisanie \ sigma w zadowalające przypisanie \ sigma ' dla \ varphi przerzucając wartość prawdy co najwyżej k zmiennych?$\varphi$$n$$\sigma : [n] \to \{0,1\}$
$k$
$\sigma$$\sigma'$$\varphi$ $k$

Problem jest wyraźnie w FPT ( Stefan Szeider: Sparametryzowana złożoność lokalnego wyszukiwania k-Flip dla SAT i MAX SAT. Optymalizacja dyskretna 8 (1): 139-145 (2011) )

Czy dopuszcza jądro wielomianowe? (przy założeniu rozsądnej złożoności)

Najnowsze techniki krzyżowania kompozycji (patrz Hans L. Bodlaender, Bart MP Jansen, Stefan Kratsch, „Kernelization Lower Bounds By Cross-Composition” ) wydają się nieużyteczne w przypadku tego problemu. Wydają się również nieprzydatne w przypadku podobnych problemów, które pytają, czy dane rozwiązanie problemu trudnego dla NP można znaleźć w danej instancji za pomocą lokalnego wyszukiwania (ograniczając wyszukiwanie do sąsiadów danej instancji, pod pewną naturalną miarą odległości).

Problem nie ma wielomianowego jądra, chyba że NP jest w CoNP / poly. Technika kompozycyjna z naszego artykułu ma zastosowanie w sposób niebanalny.

Pokażę, w jaki sposób klasyczny problem Okładki Wierzchołków OR-krzyżuje się w problem k-FLIP-SAT; na podstawie wyników w cytowanej pracy jest to wystarczające. Konkretnie budujemy algorytm czasu wielomianowego, którego dane wejściowe są sekwencją wystąpień pokrywy wierzchołków$(G_1,k), (G_2, k), \ldots, (G_t, k)$ wszystkie mają tę samą wartość $k$ i wszyscy mają dokładnie $n$wierzchołki. Dane wyjściowe to instancja$k$-FLIP SAT z wartością parametru $O(k + \log t)$, który jest wystarczająco mały, aby uzyskać kompozycję krzyżową, taką jak $k$-Instrukcja FLIP SAT ma odpowiedź tak, jeśli jeden z grafów wejściowych ma rozmiar okładki wierzchołka $k$. Duplikując jedno wejście (co nie zmienia wartości OR) możemy zapewnić, że liczba wejść$t$ jest potęgą dwóch.

Kompozycja przebiega w następujący sposób. Ponumeruj wierzchołki na wykresie dla każdego wykresu wejściowego$G_i$ tak jak $v_{i,1}, v_{i,2}, \ldots, v_{i,n}$. Utwórz odpowiednią zmienną w instancji FLIP-SAT dla każdego wierzchołka każdego wykresu wejściowego. Dodatkowo utwórz zmienną selektora$u_i$ dla każdego wejściowego numeru instancji $i \in [t]$. Dla każdego wykresu wejściowego$G_i$, dodajemy do formuły kilka klauzul. Dla każdej krawędzi$\{v_{i,x}, v_{i,y}\}$ wykresu $G_i$, dodaj klauzulę $(v_{i,x} \vee v_{i,y} \vee \neg u_i)$ do formuły, która koduje „albo jeden z punktów końcowych tej krawędzi jest ustawiony na true, albo instancja $i$ jest nieaktywny ". W początkowym przypisaniu wszystkie zmienne wierzchołków są ustawione na false i wszystkie zmienne selektora $u_i$są ustawione na false, aby wszystkie te klauzule były spełnione. Aby wbudować zachowanie OR w kompozycję, wzmocnimy formułę, aby upewnić się, że zadowalające przypisanie ustawia co najmniej jeden selektor na wartość true, a następnie musi również utworzyć osłonę wierzchołka wybranego wykresu.

Aby upewnić się, że możemy dokonać tego wyboru, zachowując niewielką odległość przerzucania w porównaniu do liczby wejść $t$, używamy struktury pełnego drzewa binarnego z $t$ liście, które ma wysokość $\log t$. Numeruj liście od$1$ do $t$ i skojarzyć $i$-ty liść ze zmienną $u_i$ która kontroluje wejście $i$jest aktywny czy nie. Utwórz nową zmienną dla każdego wewnętrznego węzła drzewa binarnego. Dla każdego węzła wewnętrznego niech będzie odpowiadająca mu zmienna$x$ a zmienne jego dwojga dzieci będą $y$ i $z$. Dodaj klauzulę$(\neg x \vee y \vee z)$ do formuły, która wychwytuje implikacje $(x \rightarrow (y \vee z))$, wymuszając to $x$może być prawdą tylko wtedy, gdy jedno z jego dzieci jest prawdą. Aby uzupełnić formułę, dodaj klauzulę singleton, mówiącą, że zmienna węzła głównego drzewa binarnego musi być prawdziwa. W początkowym przypisaniu prawdy wartości wszystkich zmiennych dla wewnętrznych węzłów są ustawione na false, co spełnia wszystkie klauzule formuły, z wyjątkiem klauzuli singleton wymagającej, aby węzeł główny drzewa miał zmienną true.

To uzupełnia opis formuły i przypisania prawdy. Ustaw parametr$k'$ problemu FLIP DISTANCE, który ma być równy $(k + \log t + 1)$, która jest odpowiednio ograniczona dla kompozycji krzyżowej. Pozostaje pokazać, że możemy przewrócić$k'$ zmienne, aby formuła była prawdziwa w niektórych grafach wejściowych $G_i$ ma rozmiar okładki wierzchołka $k$.

Załóżmy, że w odwrotnym kierunku $G_i$ ma rozmiar$k$pokrywa wierzchołka. Ustaw$k$ zmienne odpowiadające $k$wierzchołki w okładce do prawdziwej, odwracając je. Ustaw zmienną selektora$u_i$ na true, aby zakodować to wejście $i$ jest aktywowany i odwraca zmienne $\log t$ wewnętrzne binarne węzły drzewa na ścieżce liścia $i$do korzenia na prawdę. Łatwo jest zweryfikować, czy jest to zadowalające zadanie: wszystkie implikacje w drzewie binarnym są spełnione, wartość węzła głównego jest ustawiona na true, klauzule sprawdzające krawędzie$G_{i'}$ dla $i' \neq i$ pozostają zadowoleni, ponieważ $u_{i'}$ pozostaje fałszywe, podczas gdy klauzule dotyczące wykresu $G_i$ są zadowoleni, ponieważ dla każdej krawędzi ustawiamy co najmniej jeden punkt końcowy na true.

Dla kierunku do przodu załóżmy, że formuła może być spełniona przez co najwyżej odwrócenie $k + \log t + 1$zmienne. Następnie musimy przestawić zmienną węzła głównego na true. Implikacje w drzewie binarnym wymuszają, że przynajmniej jedna zmienna selektora liścia jest ustawiona na true, powiedzmy$u_i$. Aby zaspokoić implikacje zakodowane w drzewie binarnym, wszystkie wewnętrzne węzły na ścieżce od$u_i$ do katalogu głównego ustawiono wartość true, uwzględniając $1 + \log t$przewraca Od$u_i$ jest ustawione na true, klauzule wykonane dla wykresu $G_i$ nie są usatysfakcjonowani dosłownie $\neg u_i$, więc są zadowoleni, ponieważ jeden z punktów końcowych każdej krawędzi $G_i$ma wartość true. A przynajmniej$1 + \log t$ zmienne drzewa binarnego zostały co najwyżej odwrócone $k$zmienne wierzchołków są odwracane do wartości true w tym rozwiązaniu. To koduje rozmiar okładki wierzchołka$k$ w $G_i$i dowodzi, że jednym z danych wejściowych jest instancja TAK. To kończy dowód.