Czy SAT w ograniczonej szerokości jest rozstrzygalny w przestrzeni logów?

Elberfeld, Jakoby i Tantau 2010 ( ECCC TR10-062 ) dowiodły, że zajmująca mało miejsca wersja twierdzenia Bodlaendera. Wykazali, że w przypadku wykresów o szerokości co najwyżej rozkład drzewa o szerokości można znaleźć za pomocą przestrzeni logarytmicznej. Stały współczynnik w ograniczonej przestrzeni zależy od . (Twierdzenie Bodlaendera pokazuje liniowe ograniczenie czasowe z wykładniczą zależnością od w współczynniku stałym). $k$ $k$ $k$ $k$

SAT staje się łatwy, gdy zestaw klauzul ma małą szerokość. W szczególności Fischer, Makowsky i Ravve 2008 wykazali, że o zadowalalności wzorów CNF z szerokością wykresu występowania ograniczonego przez można decydować co najwyżej operacji arytmetycznych, gdy podany jest rozkład drzewa. Zgodnie z twierdzeniem Bodlaendera obliczenie rozkładu drzewa wykresu padania dla ustalonego może być wykonane w czasie liniowym, a zatem SAT można ustalić dla ograniczonych wzorów szerokości w czasie, który jest wielomianem niskiego stopnia w liczbie zmiennych . $k$ $2^{O(k)} n$ $k$ $n$

Można zatem oczekiwać, że SAT powinien być rzeczywiście rozstrzygalny przy użyciu przestrzeni logarytmicznej, dla formuł o ograniczonej szerokości wykresu częstości. Nie jest jasne, jak zmodyfikować Fischera i in. podejście do decydowania o SAT w czymś zajmującym mało miejsca. Algorytm działa poprzez obliczenie wyrażenia liczby rozwiązań, poprzez włączenie-wykluczenie i rekurencyjną ocenę liczby rozwiązań o mniejszych formułach. Chociaż ograniczona szerokość grzbietu pomaga, podformuły wydają się zbyt duże, aby obliczyć je w przestrzeni logarytmicznej.

To prowadzi mnie do pytania:

Czy wiadomo, że SAT dla formuł o ograniczonej krzyżówce występuje w lub ? $\mathsf{L}$ $\mathsf{NL}$

— András Salamon
źródło

Czy fakt, że SAT w L dla ograniczonych przypadków szerokości pleców nie wynika bezpośrednio z wyników w cytowanym artykule? Zestaw zadowalających wzorów można zdefiniować w MSO. Dlatego satysfakcję można rozwiązać w czasie liniowym na wykresach ograniczonej szerokości za pomocą twierdzeń Bodlaender + Courcelle. Elberfeld-Jakoby-Tantau-2010, pokazują, że właściwości MSO można decydować w przestrzeni logarytmicznej na wykresach ograniczonej szerokości, dostarczając logarytmiczne wersje twierdzeń Bodlaendera + Courcelle'a. Dlatego SAT może być ustalany w przestrzeni logów na wykresach ograniczonej szerokości.

— Mateus de Oliveira Oliveira

@MateusdeOliveiraOliveira, szczegóły nie wydają mi się jasne. SAT jest definiowalny przez MSO za pomocą struktury o dwóch ukierunkowanych relacjach krawędzi (Immerman Przykład 2.18), których połączenie prowadzi do krawędzi wykresu zapadalności po zapomnieniu kierunku. Nie jest dla mnie jednak jasne, czy można zastosować wykres częstości występowania w celu zdefiniowania przez MSO satysfakcji (na przykład poprzez zestaw ubezpieczenia), aby móc zastosować Bodlaender / Courcelle / EJT.

— András Salamon

@ AndrásSalomon Twierdzenie Courcelle'a można przedstawić dla wykresów z kolorowymi wierzchołkami i krawędziami. Szerokość takich kolorowych wykresów jest taka sama jak szerokość bezbarwnych wersji. Istnieje wiele sposobów modelowania dowolnych struktur relacyjnych jako kolorowych wykresów.

— Mateus de Oliveira Oliveira

W przypadku formuł chcesz zdefiniować strukturę relacyjną, która jednocześnie koduje formułę i wykres występowania. (w przeciwnym razie, w jaki sposób zdefiniowalibyście satysfakcję na pierwszym miejscu?) Następnie, stosując odpowiednie pojęcie szerokości poprzecznej dla takiej struktury, otrzymujemy, że szerokość poprzeczna struktury (wykres Formula + Częstotliwość) jest co najwyżej stałą addytywną większą niż szerokość poprzeczna sam wykres częstości. Zauważ, że istnieje wiele sposobów definiowania takich połączonych struktur relacyjnych i zasadniczo każdy autor używa tego, który jest najbardziej odpowiedni dla jego kontekstu.

— Mateus de Oliveira Oliveira

@ Mateusz, dziękuję! To raczej pomocny komentarz; Nie zdawałem sobie sprawy z natury „przybornika” szerokości w opisowej złożoności. Chcesz zamienić to w odpowiedź?

— András Salamon

Rzeczywiście, korzystając z wyników w Elberfeld-Jakoby-Tantau-2010, można wykazać, że o SAT można decydować w przestrzeni logicznej na formułach, których wykres występowania ograniczył szerokość. Oto szkic głównych kroków dowodu tego roszczenia.

Pojęcia rozkładu drzewa i szerokości drzewa można uogólnić na dowolne struktury relacyjne. Patrz na przykład sekcje 2 i 3 tego artykułu autorstwa Dalmau, Kolaitis i Vardi.
Twierdzenie Courcelle'a stwierdza, że logika MSO może być ustalona w czasie liniowym na relacyjnych strukturach o stałej szerokości.
$t$ $f(t)\cdot n$
$\tau$ $F$ $I$ $\tau$ $I$
$\tau$
Dlatego, według twierdzenia Bodlandera + Courcelle'a, można zdecydować, czy formuła stałej szerokości poprzecznej jest zadowalająca w czasie liniowym.
Elberfeld-Jakoby-Tantau-2010 pokazuje, że „czas liniowy” można zastąpić „przestrzenią logarytmiczną” zarówno w twierdzeniu Bodlaendera, jak i Courcelle'a.
$\varphi$ $\tau$ $\tau$ $\varphi$
W szczególności SAT można określić w przestrzeni logów na wykresach stałej szerokości.

— Mateus de Oliveira Oliveira
źródło