Jak wydajne są solwery SAT oparte na DPLL w zadowalających instancjach PHP?

Wiemy, że DPLL oparte SAT-rozwiązują nie odpowie poprawnie na unsatisfiable wystąpień (zasada dziura gołąb), np na „nie jest injective mapowanie od do ”: $\mathrm{PHP}$ $n+1$ $n$

P. H. {P.}_{n}^{n + 1} : = (\underset{ja \in [n + 1]}{⋀} \underset{jot \in [n]}{⋁} p_{ja, jot}) \land (\underset{ja \neq {ja}^{'} \in [n + 1]}{⋀} \underset{jot \in [n]}{⋀} (\neg p_{ja, jot} \lor \neg p_{{ja}^{'}, jot}))

$\mathrm{PHP^{n+1}_{n}} := \left(\bigwedge_{i\in[n+1]} \ \bigvee_{j\in[n]} \ p_{i,j}\right) \wedge \left(\bigwedge_{i\neq i'\in[n+1]} \ \bigwedge_{j\in[n]} \ (\lnot p_{i,j} \vee \lnot p_{i',j})\right)$

Szukam wyników na temat tego, jak działają na zadowalających przypadkach , np. Na „istnieje iniekcyjne mapowanie od do ”. $\mathrm{PHP}$ $n$ $n$

Czy szybko znajdują satysfakcjonujące zadanie w takich przypadkach?

cc.complexity-theory lo.logic proof-complexity

— Kaveh
źródło

Przez „nie odpowiedzieć poprawnie” masz na myśli „zabrakło zasobów na wystarczająco dużych wartościach n”?

— Vijay D

@Kaveh Czy zezwalasz na powtarzanie klauzul i / lub powtarzanie zmiennych w tej samej klauzuli? Dzięki

— Tayfun Zapłać

@VijayD, mam na myśli, że algorytm nie zwraca poprawnej odpowiedzi w czasie wielomianowym dla wystarczająco dużej liczby

. Mam nadzieję, że da się udowodnić, że algorytm oparty na DPLL będzie działał w czasie wielomianowym w tej rodzinie.

n

$n$

— Kaveh

@Geekster, nie jestem pewien, co masz na myśli. Mam szczególną rodzinę formuł. Czy pytasz, czy w tej formule jest powtórzenie?

— Kaveh

Na spe przypadkach , DPLL na podstawie rozwiązują SAT dostarczy satysfakcjonujące zadanie w czasie liniowo. $PHP$

Aby zobaczyć, dlaczego, obserwuj, w jaki sposób kodowanie CNF niezadowalającego wystąpienia z dziurami i gołębiami jest sintaktycznie identyczne z wystąpieniem Wykres koloryzacji , gdzie grafem wejściowym jest klika wierzchołków . $PHP$ $n$ $n + 1$ $k = n$ $n + 1$

Podobnie CNF zakodowanie spe wystąpienia z otwory, a gołębi sintactically identyczne do wystąpienia wykres barwiących, przy czym wykres wejściowy jest klika wierzchołków. $PHP$ $n$ $n$ $k = n$ $n$

Teraz kolorowanie kliki wierzchołków za pomocą kolorów jest proste: zeskanuj wierzchołki i przypisz każdemu z nich jeden z pozostałych kolorów (już przypisane kolory są automatycznie wykluczane przez kliknięcie wykresu przy użyciu propagacji jednostkowej) . Niezależnie od pozostałych wybranych kolorów, będzie on dobry i doprowadzi Cię do zadowalającego zadania. $n$ $n$

Z punktu widzenia solvera DPLL: za każdym razem, gdy spróbuje odgadnąć wartość logiczną zmiennej , taka wartość będzie poprawna (cokolwiek to jest), ponieważ z pewnością będzie zadowalające przypisanie, w której zmienna ma odgadnięta wartość. Rozmnażanie jednostek wykona resztę zadania, prowadząc solver wzdłuż satysfakcjonującej ścieżki (innymi słowy: zapobiegając odgadnięciu niewłaściwych wartości). $v_i$ $v_i$

Wyszukiwanie przebiega następnie jedna zmienna po drugiej, liniowo, za każdym razem poprawnie zgadując.

— Giorgio Camerani
źródło

Dziękuję, tego się spodziewałem. Nawiasem mówiąc, czy znasz odniesienie, które to stwierdza (tj. „Algorytm DPLL rozwiązuje zadowalające wystąpienia PHP / GC w czasie liniowym”)?

— Kaveh

Zapraszamy. Nie znam żadnego odniesienia, które by to stwierdzało, właśnie wyprowadziłem to sam przez jakieś surowe rozumowanie. Formalne udowodnienie tego nie powinno być trudne, opierając się na fakcie, że każdy solver SAT używa pewnej rozsądnej heurystyki zarówno przy wybieraniu następnej zmiennej, jak i odgadywaniu jej wartości logicznej. W rzeczywistości należy zauważyć, że istnieje co najmniej jedna nierozsądna heurystyka, która uniemożliwia nam znalezienie rozwiązania w czasie liniowym (taka nieracjonalna heurystyka byłaby ustawiona na fałsz każdej zmiennej, aż będzie to możliwe). Przy rozsądnej heurystyce zapewniony jest czas liniowy.

— Giorgio Camerani

Zgadzam się. Mam nadzieję, że ktoś mógł to gdzieś powiedzieć, żebym mógł zacytować, kiedy będę potrzebować. Chciałbym poczekać jeszcze kilka dni i jeśli nikt nie poda referencji, zaakceptuję tę odpowiedź. Dzięki jeszcze raz. :)

— Kaveh

Cała przyjemność po mojej stronie ;-) Pozdrawiam!

— Giorgio Camerani