Czy SAT jest językiem bezkontekstowym?

Rozważam język wszystkich zadowalających formuł logicznych zdań, SAT (aby upewnić się, że ma to skończony alfabet, będziemy kodować litery zdań w odpowiedni sposób [edytuj: odpowiedzi wskazały, że odpowiedź na pytanie może nie być solidna pod różne kodowania, więc trzeba być bardziej szczegółowym - patrz moje wnioski poniżej] ). Moje proste pytanie brzmi:

Czy SAT jest językiem bezkontekstowym?

Po raz pierwszy zgadłem, że dzisiejsza (na początku 2017 r.) Odpowiedź powinna brzmieć: „Nikt nie wie, ponieważ dotyczy to nierozwiązanych pytań w teorii złożoności”. Nie jest to jednak do końca prawdą (patrz odpowiedź poniżej), choć nie do końca fałszywe. Oto krótkie podsumowanie rzeczy, które wiemy (zaczynając od oczywistych rzeczy).

SAT nie jest regularny (ponieważ nawet składnia logiki zdań nie jest regularna z powodu pasujących nawiasów)
SAT jest kontekstowy (nie jest trudno podać dla niego LBA)
SAT jest NP-kompletny (Cook / Levin), a w szczególności decydują niedeterministyczne TM w czasie wielomianowym.
SAT może być również rozpoznawany przez jednokierunkowe niedeterministyczne automaty stosu (1-NSA) (patrz Rundy WC, Złożoność rozpoznawania w językach pośrednich , Teoria przełączania i automatu, 1973, 145-158 http://dx.doi.org/ 10.1109 / SWAT.1973.5 )
Problem słowny dla języków bezkontekstowych ma swoją własną klasę złożoności (patrz https://complexityzoo.uwaterloo.ca/Complexity_Zoo:C#cfl ) $\textbf{CFL}$
$\textbf{CFL}\subseteq\textbf{LOGCFL}\subseteq\textbf{AC}^{\textbf{1}}$ , gdzie to klasa problemów w obszarze logów, które można sprowadzić do (patrz https : //complexityzoo.uwaterloo.ca/Complexity_Zoo: L # logcfl ). Wiadomo, że . $\textbf{LOGCFL}$ $\textbf{CFL}$ $\textbf{NL}\subseteq\textbf{LOGCFL}$
Nie wiadomo, czy czy (w rzeczywistości nawet jest otwarty; myślę, że dostałem to od S. Arory, B. Baraka: Złożoność obliczeniowa: nowoczesne podejście ; Cambridge University Press 2009). W związku z tym nie może istnieć żaden problem związany z którym wiadomo, że nie występuje w . Dlatego musi być nieznane, czy SAT znajduje się w . $\textbf{NL}\subsetneq\textbf{NP}$ $\textbf{NL}=\textbf{NP}$ $\textbf{NC}^{\textbf{1}}\subsetneq\textbf{PH}$ $\textbf{NP}$ $\textbf{LOGCFL}$ $\textbf{LOGCFL}$

Jednak ten ostatni punkt wciąż pozostawia możliwość, że wiadomo, że SAT nie znajduje się w . Ogólnie rzecz biorąc, nie mogłem znaleźć wiele na temat związku z hierarchią który mógłby pomóc wyjaśnić epistemiczny status mojego pytania. $\textbf{CFL}$ $\textbf{CFL}$ $\textbf{NC}$

Uwaga (po zapoznaniu się z kilkoma wstępnymi odpowiedziami): Nie oczekuję, że formuła będzie miała normalną spójną postać (nie zmieni to istoty odpowiedzi i zwykle nadal mają zastosowanie argumenty, ponieważ CNF jest również formułą. twierdzą, że wersja problemu o stałej liczbie zmiennych jest normalna, ponieważ nie trzeba składać nawiasów).

Wniosek: W przeciwieństwie do moich domysłów inspirowanych teorią złożoności, można bezpośrednio pokazać, że SAT nie jest pozbawiony kontekstu. Sytuacja jest zatem następująca:

Wiadomo, że SAT nie jest pozbawiony kontekstu (innymi słowy: SAT nie jest w ), przy założeniu, że stosuje się „bezpośrednie” kodowanie formuł, w których zmienne zdań są identyfikowane przez liczby binarne (i niektóre dalsze symbole są używane dla operatorów i separatorów). $\textbf{CFL}$
Nie wiadomo, czy SAT znajduje się w , ale „większość ekspertów myśli”, że tak nie jest, ponieważ oznaczałoby to . Oznacza to również, że nie wiadomo, czy inne „rozsądne” kodowania SAT są pozbawione kontekstu (zakładając, że uznalibyśmy przestrzeń logiczną za akceptowalną próbę kodowania w przypadku problemu trudnego dla NP). $\textbf{LOGCFL}$ $\textbf{P}=\textbf{NP}$

Zauważ, że te dwa punkty nie oznaczają . Można to pokazać bezpośrednio, pokazując, że w (a więc w ) istnieją języki, które nie są pozbawione kontekstu (np. ). $\textbf{CFL}\subsetneq\textbf{LOGCFL}$ $\textbf{L}$ $\textbf{LOGCFL}$ $a^nb^nc^n$

— mak
źródło

Jeśli tak, to P = NP.

— Ryan

Gdyby SAT były pozbawione kontekstu, wówczas programowanie dynamiczne (algorytm CYK) dałoby wielomianowy algorytm czasowy do testowania członkostwa w SAT, dając P = NP. Nawet P = NP nie oznaczałoby, że SAT nie zawiera kontekstu. Wydaje się, że to kodowanie zmiennych może być ważniejsze, niż można to przypisać. Nie opracowałem szczegółów, ale jeśli dodałeś do zmiennych jednoargumentowe lub binarne „indeksy”, myślę, że miałbyś problemy z rozróżnieniem (x i y) od (x i nie x) dla wystarczająco dużych indeksów.

— AdamF

Musisz dokładnie określić reprezentację, zanim zaczniesz wysuwać wnioski P = NP. Na przykład faktoring liczby N jest czasem wielomianowym w N (interesujące pytanie dotyczy liczby bitów potrzebnych do zapisania N binarnie lub o log N).

— Aryeh

Byłem świadomy wniosku P = NP i dlatego nie spodziewano się, że odpowiedź brzmi „tak” (przepraszam, że jestem trochę prowokujący w tym, jak to sformułowałem ;-). Nadal zastanawiałem się, czy jest to naprawdę znane, czy tylko coś, w co „większość ekspertów wierzy” (odpowiedzi jasno wskazują teraz, że to pierwsze jest prawdziwe; wybiorę jeden we właściwym czasie).

— mak

Odpowiedzi:

Tylko alternatywny dowód z wykorzystaniem kombinacji dobrze znanych wyników.

Przypuszczam, że:

zmienne są wyrażane wyrażeniem regularnym $d = (+|-)1(0|1)^*$
i że ( zwykły ) język (ponad używany do reprezentowania formuł CNF to: ; pamiętaj tylko, że pobiera wszystkie prawidłowe formuły CNF aż do zmiany nazwy. $\Sigma = \{0,1,+,-,\land,\lor\})$ $S = \{ d^+ (\lor d^+)^*(\land (d^+ (\lor d^+)^*))^* \}$ $S$

Na przykład jest zapisany jako: ( operator ma pierwszeństwo przed ) . $\varphi = (x_1 \lor x_2) \land -x_3$ $s_{\varphi} = +1 \lor +10 \land -11 \in S$ $\lor$ $\land$

Załóżmy, że odpowiednia formuła jest zadowalająca to CF. $L = \{ s_{\varphi} \in S \, \mid$ $\varphi$ $\}$

Jeśli przecinamy go zwykłym językiem: nadal otrzymujemy język CF. Możemy również zastosować homomorfizm: , a językiem pozostaje CF. $R = \{ +1^a \land -1^b \land -1^c \mid a,b,c > 0 \}$ $h(+) = \epsilon$ $h(-) = \epsilon$

Ale język, który otrzymujemy to: , ponieważ jeśli to formuła „source” jest co jest niezadowalające (podobnie jeśli ). Ale jest dobrze znanym językiem innym niż CF Sprzeczność z . $L' = \{ 1^a \land 1^b \land 1^c \mid a \neq b, a \neq c\}$ $a=b$ $+x_a \land -x_a \land -x_b$ $a=c$ $L'$ $\Rightarrow$

— Marzio De Biasi
źródło

Przyjąłem tę odpowiedź teraz, ponieważ nadal istnieje otwarty problem z drugim podejściem (patrz komentarze) i podoba mi się nieco bardziej podstawowy argument. Warto podkreślić, że argument jest specyficzny dla wybranego kodowania i rzeczywiście nie wiadomo, czy można znaleźć inne proste kodowanie (logspace), które prowadzi do języka bezkontekstowego.

— mak

@mak: Podejrzewam, że każde inne „rozsądne” kodowanie SAT może być niezgodne z CF przy użyciu podobnej techniki. Być może innym interesującym kierunkiem byłoby zbadanie, czy możemy zastosować jakąś diagonalizację w celu uzyskania bardziej ogólnego dowodu: formuła SAT koduje obliczenia symulujące automaty wypychające na danym wejściu i jest zadowalające tylko wtedy, gdy nie jest akceptuję to. Ale to tylko niewyraźny pomysł ...

— Marzio De Biasi

Sprawdzanie, czy łańcuch jest w zwykłym języku, znajduje się w P. Załóżmy, że SAT było w Reg. Wtedy NP = coNP. Niech L będzie w Reg. Rozważmy formułę, która jest prawdziwa, jeśli nie ma jej w L. Jest w NP, więc można ją wyrazić jako formułę SAT. Jest w języku, jeśli nie jest.

— Kaveh

Jeśli liczba zmiennych jest skończona, to również liczba zadowalających koniunkcji, więc twój język SAT jest skończony (a zatem regularny). [Edytuj: roszczenie to przyjmuje formę CNFSAT.]

W przeciwnym razie zgódźmy się na kodowanie formuł takich jak przez . Użyjemy lematu Ogdena, aby udowodnić, że język wszystkich zadowalających spójników nie jest pozbawiony kontekstu. $(x_{17}\vee \neg x_{21})\wedge (x_{1}\vee x_{2}\vee x_3)$ $(17+\tilde{} 21)(1+2+3)$

Niech będzie stałą „zaznaczania” w lemacie Ogdena i rozważmy wzór sat którego pierwsza klauzula składa się z - to znaczy kodowania , gdzie jest liczbą dziesiętną składającą się z te. Zaznaczamy jednymi z , a następnie wymagać, aby wszyscy pumpings z odpowiedniego rozkładu (patrz zawarcia lematu Ogdena jest) być również spełnialna. Ale możemy to łatwo zablokować, wymagając, aby żadna klauzula zawierająca , gdzie jest ciągiem krótszym niż $p$ $w$ $(1^p)$ $(x_N)$ $N$ $p$ $p$ $1^p$ $w$ $x_q$ $q$ $1$ $p$ , bądź zadowalający - na przykład upewniając się, że każda inna klauzula ma negację każdego takiego . Oznacza to, że zawiedzie właściwość „negatywnego pompowania” i dochodzimy do wniosku, że język nie jest pozbawiony kontekstu. [Uwaga: zignorowałem trywialne przypadki, w których podczas pompowania powstają źle uformowane łańcuchy.] $w$ $x_q$ $w$

— Aryeh
źródło

Uwaga: W moim twierdzeniu, że dla skończonej liczby zmiennych język jest skończony, domyślnie nie pozwalam na powtarzanie zmiennej w ramach klauzuli lub klauzuli bez ograniczeń wiele razy

— Aryeh

... Ale myślę, że język jest nadal regularny, ponieważ bierze się skończony zbiór formuł „zasadniczo odrębnych” (tj. Bez trywialnych powtórzeń), a następnie pozwala na różne powtórzenia.

— Aryeh

Roszczenie z regularnością działa tylko w przypadku CNFSAT (dodałem wyjaśnienie do mojego pytania).

— mak

Nawet przy dowolnych formułach innych niż CNF w skończonej liczbie zmiennych, satysfakcja (i każdy język, który nie może rozróżnić dwóch logicznie równoważnych formuł pod tym względem) jest łatwo postrzegana jako pozbawiona kontekstu. Nie dostrzegam jednak tego znaczenia. Zadowolenie formuł w skończonej liczbie zmiennych jest banalnym problemem, który nie ma nic wspólnego ze złożonością SAT.

— Emil Jeřábek

OK, widzę problem - domyślnie zakładałem, żemoże być ograniczona długością (jak w klasycznym lemacie pompującym), jednocześnie będąc w stanie określić coś o jego lokalizacji w ciągu. Myślę, że ten argument można naprawić, wykonując od nowa lemat pompowania. Sprawimy, że ta pierwsza zmienna będzie naprawdę długą sekwencją jedynek - wystarczająco długich, aby niektóre poddrzewa generujące ciągły ciąg tych jedności musiały być wystarczająco głębokie, aby zastosować zasadę pidgeonhole.

| x y z |

$|xyz|$

— Aryeh