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).

1. SAT nie jest regularny (ponieważ nawet składnia logiki zdań nie jest regularna z powodu pasujących nawiasów)
2. SAT jest kontekstowy (nie jest trudno podać dla niego LBA)
3. SAT jest NP-kompletny (Cook / Levin), a w szczególności decydują niedeterministyczne TM w czasie wielomianowym.
4. 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 )
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}$
6. LOGCFL CFL NL ⊆ $\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}$
7. 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}$NC 1 ⊊ PH NP LOGCFL $\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:

1. 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}$
2. 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).P = $\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. ).L LOGCFL a n b n c $\textbf{CFL}\subsetneq\textbf{LOGCFL}$$\textbf{L}$$\textbf{LOGCFL}$$a^nb^nc^n$

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.S = { d + ( ∨ d + ) ∗ ( ∧ ( d + ( ∨ d + ) ∗ ) ) ∗ } $\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 ) .s φ = + 1 ∨ + 10 ∧ - 11 ∈ S ∨ $\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.h ( + ) = ϵ h ( - ) = $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 .a = b + x a ∧ $L' = \{ 1^a \land 1^b \land 1^c \mid a \neq b, a \neq c\}$$a=b$ a = c L ′$+x_a \land -x_a \land -x_b$$a=c$$L'$$\Rightarrow$

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.( 17 + $(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żw ( 1 p ) ( x N ) N p p 1 p w x q q 1 $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.]x q$w$$x_q$$w$