Poprawiasz ogólną redukcję Cooka dla Clique do SAT?

Jestem zainteresowany zredukowaniem kliki do SAT bez powiększania instancji. $k$

Klika jest w NP, więc można ją zredukować do SAT za pomocą przestrzeni logarytmicznej. Prosta redukcja podręcznika Garey / Johnson wysadza instancję do sześciennej wielkości. Jednak Klika jest w P dla każdego ustalonego więc „powinna” być skuteczna redukcja przynajmniej dla ustalonego . $k$ $k$ $k$

Jednym ze sposobów zbudowania redukcji jest użycie zmiennych SAT jako charakterystycznego wektora , przy czym zmienna ustawiona na true wskazuje, że powiązany wierzchołek znajduje się w klikie. Ta redukcja jest naturalna, ale tworzy instancję SAT o kwadratowym rozmiarze, jeśli wykres jest rzadki. W przypadku wykresu rzadkiego potrzeba kwadratowo wielu klauzul, aby wymusić, że w każdej parze niesąsiadujących wierzchołków może znajdować się co najwyżej jeden wierzchołek kliki.

Spróbujmy zrobić lepiej niż . $O(n^2)$

Ogólną redukcję Kucharz / Schnorr / Pippenger / Fischer pracuje najpierw biorąc wielomianowo czas ograniczony NDTM który decyduje się języka, symulując NDTM przez zważając DTM, symulując niepomny DTM przez obwód, a następnie symulację obwodu przez 3 -Sat wystąpienie. Powoduje to utworzenie instancji 3-SAT o rozmiarze jeśli czasowe ograniczenie NDTM wynosi . Współczynnik logarytmiczny wydaje się nieunikniony z powodu narzutu podczas symulacji przez nieświadomą maszynę. Dla kliki wydaje się, że ma $O(t(n)\log t(n))$ $t(n)$ $k$ , co daje instancję 3-SAT o wielkości , która jestquasilineardla stałej . W swoim artykule z 1988 roku Cook zapytał, czy istnieje lepsza ogólna redukcja dla języków w NP, i o ile wiem, jest to nadal otwarte. Jednak Clique ma wiele struktur, więc być może lepiej poradzić sobie w tym przypadku. $t(n) = O(nk)$ $O(nk(\log n + \log k))$ $k$

Czy jest znana lepsza redukcja z Clique do SAT?

$k$ $k$

(Pracowałem z redukcją, która wydaje się unikać czynnika logarytmicznego, ale przed marnowaniem więcej czasu na krwawe szczegóły, aby zweryfikować jej poprawność, chciałbym wiedzieć, czy taka redukcja jest już znana, czy też jest mało prawdopodobne, aby istnieć.)

— András Salamon
źródło

k

$k$

k

$k$

k

$k$

k

$k$

k

$k$

k \log n

$k\log n$

k \log n

$k\log n$

k

$k$

k

$k$

$k$ $O(nk)$ $O(nk^2)$ $k$ $n$

$x_{iv}=1$ $v$ $i$ $x_i$ $i$ $nk$

$(i,j)$ $n$ $(\neg x_{iu} \lor x_{jv_1} \lor \dots \lor x_{jv_m})$ $v_1,\dots,v_m$ $u$ $u$ $O(nk^2)$

$i$ $x_i$ $x_i < x_{i+1}$ $O(n)$ $O(nk)$

$k \lg n$ $\lg n$ $i$ $k$ $k(k-1)/2$ $O((n+m+k^2) \text{poly}(\lg n))$ $m =$

— DW
źródło