Czy są jakieś trudne przypadki 3-SAT, gdy klauzule mogą używać tylko literałów, które są „w pobliżu”?

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 $x_1 , x_2 , x_3 ... x_n$$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 $(x_a , x_b, x_c)$$d(x_a , x_b) \leq N \wedge d(x_a , x_c) \leq N \wedge d(x_b , x_c) \leq 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.

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 ) $m$$O(m 2^N)$$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$$\varphi_i$$x_1,\dots,x_i$$S_i \subseteq \{0,1\}^n$$x_{i-N},x_{i-N+1},\dots,x_i$$\varphi_i$$S_{i-1}$$S_i$$O(2^N)$ 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$(x_{i-N-1},\dots,x_{i-1}) \in S_{i-1}$$x_i$$\varphi_i$$x_i$; 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.$(x_{i-N},\dots,x_{i})$$S_i$$i$$S_i$$m$$S_m \ne \emptyset$$O(2^N)$$m$$O(m 2^N)$

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 ) $t$$O(m 2^{(t+1)N})$$t$

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 .