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

22

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 |x1,x2,x3...xnd(xa,xb)=|ab|

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(xa,xb,xc)d(xa,xb)Nd(xa,xc)Nd(xb,xc)NN

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.

IIAOPSW
źródło
2
„Ciężko mam na myśli, że heurystyczny solver powróciłby do najgorszego przypadku”. nie brzmi dla mnie dobrze zdefiniowane. Czy możemy zinterpretować twoje pytanie jako pytanie, czy istnieje algorytm czasu wielomianowego, który rozwiązuje wszystkie takie instancje 3-SAT? Lub pytasz o złożoność / twardość tego problemu?
DW
„Czy możemy zinterpretować twoje pytanie jako pytanie, czy istnieje algorytm czasu wielomianowego, który rozwiązuje wszystkie takie instancje 3-SAT?” Myślę, że tego właśnie szukam.
IIAOPSW
1
Stosowany wymóg lokalizacji jest również znany jako 1D „geometryczny lokalnie” i jest dominującym znaczeniem „lokalizacji” dla fizyków. Teraz, jeśli ktoś uogólni twoje pytanie na przypadek kwantowy i od bitów (2 stany) do cząstek z 8 stanami, kwantowa wersja twojego problemu jest rzeczywiście kompletna pod względem QMA („kwantowa NP”) w 1D: patrz arxiv.org/ abs / 1312.1469 W przypadku kubitów problemem jest ukończenie QMA w 2D. arxiv.org/abs/quant-ph/0504050
Martin Schwarz
4
Ach, więc to prawda, że ​​fizyk nie może się ukryć wśród informatyków. Masz mnie. Dlaczego potrzebujesz 8 stanów? Po prostu używaj kubitów, trzykrotnie powiększaj sąsiedztwo i używaj co 3 kubity do kodowania cząsteczki 8-stanowej.
IIAOPSW,
1
Jasne, ale masz dość dużą lokalizację, tzn. Twoi lokalni operatorzy obejmują wiele kubitów. Ta linia badań skupiła się również na minimalizacji miejscowości (najlepiej 2-lokalnych) kosztem cząstek o większych wymiarach i związanych z tym kompromisów.
Martin Schwarz,

Odpowiedzi:

30

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 ) NmO(m2N)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φix1,,xiSi{0,1}nxiN,xiN+1,,xiφiSi1SiO(2N) x i φ i x i ( x i - N ,, x i ) S i i S i m S mO( 2 N )mO(m 2 N )(xiN1,,xi1)Si1xiφixi; 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.(xiN,,xi)SiiSimSmO(2N)mO(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 ) ttO(m2(t+1)N)t

DW
źródło
16

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 .

Saeed
źródło
1
W rzeczywistości nawet pierwotny wykres (jedna krawędź między dwoma wierzchołkami, jeśli występują w tej samej klauzuli) ograniczył w tym przypadku szerokość ścieżki. Zobacz także (1), która może być bardziej dostępna lub odpowiedź @DW, która jest mniej więcej tym samym pomysłem jak te algorytmy. (1) Algorytmy do zliczania modeli propozycyjnych , Marko Samer, Stefan Szeider, J. Discrete Algorytmy, tom 8, numer 1, strony 50-64, 2010.
holf