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

15

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 n + 1 do n ”:P.H.P.n+1n

P.H.P.nn+1: =(ja[n+1] jot[n] pja,jot)(jaja[n+1] jot[n] (¬pja,jot¬pja,jot))

Szukam wyników na temat tego, jak działają na zadowalających przypadkach , np. Na „istnieje iniekcyjne mapowanie od n do n ”.P.H.P.nn

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

Kaveh
źródło
1
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
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

Odpowiedzi:

14

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

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

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

Teraz kolorowanie kliki wierzchołków za pomocą n 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.nn

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 v i 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).vjavja

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
1
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