Czy osadzenie rozwiązania jest możliwe dla SAT?

Interesują mnie „twarde” pojedyncze przypadki problemów z NP.

Ryan Williams omówił problem SAT0 na blogu Richarda Liptona . SAT0 pyta, czy instancja SAT ma konkretne rozwiązanie składające się ze wszystkich zer. To skłoniło mnie do myślenia o konstruowaniu instancji SAT, które prawdopodobnie będą „trudne”.

Rozważmy wystąpienie SAT z klauzulami i n zmiennymi, gdzie \ alpha = m / n jest „wystarczająco duży”, w tym sensie, że wpada do regionu poza przejściem fazowym, gdzie prawie wszystkie wystąpienia są niezadowalające. Niech x będzie losowym przypisaniem wartości \ phi .$\phi$$m$$n$$\alpha = m/n$$x$$\phi$

Czy można zmodyfikować $\phi$ aby uzyskać nową instancję $\phi|x$ , tak aby $\phi|x$ było „w dużej mierze podobne” do $\phi$ , ale aby $x$ było zadowalającym przypisaniem dla $\phi|x$ ?

Na przykład, można spróbować dodać do każdej klauzuli losowo wybrany literał z rozwiązania, który nie występuje już w tej klauzuli. To zagwarantuje, że $x$ jest rozwiązaniem.

A może jest to beznadziejne, prowadzące do szybkiego algorytmu znajdowania „ukrytego” rozwiązania, zgodnie z poniższym ostatnim pismem?

• Uriel Feige i Dorit Ron, Znalezienie ukrytych klików w czasie liniowym , DMTCS proc. AM, 2010, 189–204.

Zdaję sobie sprawę z dyskusji Cooka i Mitchella i pracy, do której się odnoszą. Nie mogłem jednak znaleźć niczego na temat tego, co dzieje się ze strukturą formuły, gdy ktoś próbuje jawnie osadzić w niej zadowalające zadanie. Jeśli to jest folklor, wskaźniki byłyby bardzo mile widziane!

• Stephen A. Cook i David G. Mitchell, Znalezienie trudnych przypadków problemu satysfakcji: ankieta , seria DIMACS w dyskretnej matematyce i informatyce teoretycznej 35 1–17, AMS, ISBN 0-8218-0479-0, 1997. ( PS )

Możesz wziąć dowolną formułę i zmienić ją na formułę gdzie jest „twardą” instancją SAT, której jedynym rozwiązaniem jest . Jednym ze sposobów skonstruowania takiej formuły jest zastosowanie kryptografii: jeśli jest permutacją jednokierunkową, wybieramy losowo i ustawiamy , wówczas można przekonwertować na wzór SAT tak, że jest jego jedynym rozwiązaniem, a zatem znalezienie odpowiada odwróceniu . (Potrzebujemy, aby był losowy, ale to coś podobnego jest zakładane, jeśli myślimy o znalezieniuφ ∨ ψ x ψ x x f : { 0 , 1 } n → { 0 , 1 } n x y = f ( x ) y x x f f x $\varphi$$\varphi \vee \psi_x$$\psi_x$$x$$f:\{0,1\}^n\rightarrow \{0,1\}^n$$x$$y=f(x)$$y$$x$$x$$f$$x$$x$ powinno być trudne.)

Jeśli dobrze rozumiem sam rdzeń twojego pytania, chcesz wziąć stosunkowo łatwą instancję (ponieważ umieścisz się w obszarze, w którym ), i przekształcisz go w trudny, osadzając rozwiązanie. Wątpię, żeby to zadziałało.$\frac{m}{n}> 4.3$

Dane doświadczalne sugerują, że podczas konstruowania losową Wystąpienie „około” roztworu predefiniowanego , taki przypadek będzie łatwiejsza niż zwykle (w porównaniu do podobnych przypadkach, mających ten sam n i m ). To tak, jakby ukryte rozwiązanie pomaga rozwiązaniu SAT, prowadząc je przez przestrzeń wyszukiwania. Zwykle w celu skonstruowania takiego wystąpienia generujemy losowe klauzule jak zwykle (np. Losowo wybierając k literałów i negując każdą z nich z prawdopodobieństwem p = $x$$n$$m$$k$ ) ale odrzucamy te klauzule, które nie są spełnione przez nasze ukryte rozwiązaniex. Co dotyczy twojego podejścia do konstruowaniaϕ| xi trudna instancjaϕ: Nigdy tego nie próbowałem, ale „czuję”, żeϕ| xstanie się łatwiejszy, jeśli nie trywialny. Wierzę, że zrobienie tego zwiększyłoby liczbę trafieńliterałówx(liczba trafień literałuljest liczbą wystąpieńlwdanej formule) i że doprowadziłoby to solver SAT do celu. Może przestrzenie rozwiązaniaϕiϕ| $p = \frac{1}{2}$$x$$\phi|x$$\phi$$\phi|x$$x$$l$$l$$\phi$$\phi|x$byłyby podobne (jeśli nie prawie identyczne), jak dzieje się w przykładzie SAT0 Ryana Williamsa (prawie identyczne przestrzenie rozwiązań, ale zupełnie inna twardość). Czy próbowałeś swojego podejścia w praktyce? Interesujące byłoby zobaczyć, jak zachowuje się ten sam solver SAT na i na ϕ | x .$\phi$$\phi|x$

EDYCJA 1 (23 września 2010 r.): Po odrobinie zastanowienia czuję, że tak naprawdę przestrzeń rozwiązania byłaby bardzo różna od ϕ . Dodajesz literał do każdej klauzuli, więc dajesz większy stopień swobody takim klauzulom (tj. Każda klauzula ma większą szansę na spełnienie): prawdopodobnie uzyskana przestrzeń rozwiązania zostałaby masowo przekształcona.$\phi|x$$\phi$

EDYCJA 2 (1 października 2010): Myślałem o następującym bardzo prostym i nie oryginalnym pomyśle. Biorąc pod uwagę początkową instancję i przypisanie x :$\phi$$x$

1. Usuń z wszystkie te klauzule, które nie są spełnione przez x . To powiększy przestrzeń rozwiązania i powinno osadzić w niej x .$\phi$$x$$x$

2. Załóżmy, że usunąłeś klauzule . Teraz losowo dodaj m x nowych klauzul, uważając, aby nie były niezadowolone z x (to ponownie zawęzi przestrzeń rozwiązania, ale bez wypychania x ).$m_x$$m_x$$x$$x$

Nie wiem czy to zadziała czy nie. Jeszcze tego nie próbowałem. Mówiąc dokładniej, nie jestem pewien, czy krok 1 zawsze udaje się osadzić w przestrzeni rozwiązania (może x jest wykluczone przez pewną kombinację klauzul, nawet jeśli x nie jest niezadowalająca z każdego z nich ?).$x$$x$$x$

Najlepszym sposobem na wygenerowanie trudnych wystąpień problemów z NP-zupełnością, o których wiem, jest użycie mapowania Cooka, aby zredukować starannie wybrane wystąpienia niektórych innych trudnych problemów NP (takich jak problem z dyskretnym logarytmem lub faktoryzacja liczb całkowitych) do SAT. Są to te same „trudne problemy”, które są stosowane przez matematyków w celu zapewnienia bezpieczeństwa kryptograficznego w protokołach takich jak RSA i Diffie-Hellman.