Niech zmiennymi będą . Odległość między dwiema zmiennymi jest zdefiniowana jako. Odległość między dwoma literałami jest odległością między odpowiednimi dwiema zmiennymi. d ( x a , x b ) = | a - b |
Załóżmy, że mam instancję 3-SAT taką, że dla każdej klauzuli mamy o pewnej ustalonej wartości .d ( x a , x b ) ≤ N ∧ d ( x a , x c ) ≤ N ∧ d ( x b , x c ) ≤ N N
Koncepcyjnie można to wyobrazić, że wszystkie literały są fizycznie na linii, a wszystkie klauzule nie są w stanie przekroczyć określonej długości z przyczyn fizycznych.
Biorąc pod uwagę to ograniczenie, czy są jakieś trudne przypadki 3-SAT? Jak mały mogę zrobić sąsiedztwo i nadal znajdować trudne sytuacje? Co jeśli pozwolę kilku klauzulom naruszyć to ograniczenie?
Ciężko mam na myśli, że heurystyczny solver powróciłby do najgorszego przypadku.
źródło
Odpowiedzi:
Nie. Jeśli instancja 3-SAT ma klauzule , możesz przetestować satysfakcję w czasie . Ponieważ jest stałą stałą, jest to algorytm czasu wielomianowego, który rozwiązuje wszystkie wystąpienia Twojego problemu.O ( m 2 N ) Nm O ( m 2N.) N.
Algorytm działa w etapach. Niech oznacza wzór składający się z klauzul, które używają tylko zmiennych z . Niech oznacza zbiór przypisań do które można rozszerzyć do zadowalającego przypisania dla . Zauważ, że biorąc pod uwagę , możemy obliczyć w czasie : dla każdego , wypróbowujemy obie możliwości dla i sprawdzamy, czy spełnia on wszystkie klauzule z które zawierają zmiennąφ i x 1 , … , x i S i ⊆ { 0 , 1 } n x i - N , x i - N + 1 , … , x i φ i S i - 1 S i O ( 2 N ) ( x i - N - 1 , … , x i -m φi x1,…,xi Si⊆{0,1}n xi−N,xi−N+1,…,xi φi Si−1 Si O(2N) x i φ i x i ( x i - N ,…, x i ) S i i S i m S m ≠∅O( 2 N )mO(m 2 N )(xi−N−1,…,xi−1)∈Si−1 xi φi xi ; jeśli tak, dodajemy do . W etapie obliczamy . Po zakończeniu wszystkich etapów instancja 3-SAT jest satysfakcjonująca wtedy i tylko wtedy, gdy . Każdy etap zajmuje czas i jest etapów, więc całkowity czas działania wynosi . Jest to wielomian wielkości wejściowej, a zatem stanowi algorytm wielomianowy.(xi−N,…,xi) Si i Si m Sm≠∅ O(2N) m O(m2N)
Nawet jeśli zezwolisz ustalonej liczbie klauzul na naruszenie ograniczenia, problem można rozwiązać w czasie wielomianowym. W szczególności, jeśli zlicza liczbę klauzul, które naruszają ograniczenie, możesz rozwiązać problem w czasie , najpierw wyliczając wszystkie możliwe wartości zmiennych w tych klauzulach, następnie kontynuując powyższy algorytm. Gdy jest stałą stałą, jest to czas wielomianowy. Mogą istnieć bardziej wydajne algorytmy.O ( m 2 ( t + 1 ) N ) tt O(m2(t+1)N) t
źródło
Wykres incydentu z formuły SAT jest dwustronnym wykresem, który ma wierzchołek dla każdej klauzuli i każdej zmiennej. Dodajemy krawędzie między klauzulą a wszystkimi jej zmiennymi. Jeśli wykres incydentu ograniczył szerokość, wówczas możemy zdecydować o formule SAT w P, w rzeczywistości możemy zrobić znacznie więcej. Twój wykres incydentów jest bardzo ograniczony. Np. Jest to ograniczony wykres ścieżki, więc jest to czas wielomianowy do rozwiązania. Powyżej dobrze znany wynik strukturalny, np . Patrz : https://www.sciencedirect.com/science/article/pii/S0166218X07004106 .
źródło