SAT est-il un langage sans contexte?

J'examine le langage de toutes les formules logiques propositionnelles satisfaisantes, SAT (pour garantir qu'il ait un alphabet fini, nous encoderions les lettres propositionnelles d'une manière appropriée [modifier: les réponses ont souligné que la réponse à la question peut ne pas être robuste sous différents encodages, il faut donc être plus précis - voir mes conclusions ci-dessous] ). Ma simple question est

SAT est -il un langage sans contexte?

Ma première supposition était que la réponse d'aujourd'hui (début 2017) devrait être "Personne ne sait, car cela concerne des questions non résolues dans la théorie de la complexité." Cependant, ce n'est pas vraiment vrai (voir la réponse ci-dessous), mais pas complètement faux non plus. Voici un bref résumé des choses que nous savons (en commençant par des choses évidentes).

SAT n'est pas régulier (car même la syntaxe de la logique propositionnelle n'est pas régulière, en raison des parenthèses correspondantes)
SAT est contextuel (il n'est pas difficile de lui donner un LBA)
SAT est NP-complet (Cook / Levin), et en particulier décidé par des MT non déterministes en temps polynomial.
SAT peut également être reconnu par des automates de pile non déterministes unidirectionnels (1-NSA) (voir WC Rounds, Complexity of Recognition in Intermediate Level Languages , Switching and Automata Theory, 1973, 145-158 http://dx.doi.org/ 10.1109 / SWAT.1973.5 )
Le problème de mot pour les langues sans contexte a sa propre classe de complexité $\textbf{CFL}$ (voir https://complexityzoo.uwaterloo.ca/Complexity_Zoo:C#cfl )
, où est la classe d'espace de journalisation des problèmes réductible à (voirhttps://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#logcfl). Il est connu que . $\textbf{CFL}\subseteq\textbf{LOGCFL}\subseteq\textbf{AC}^{\textbf{1}}$ $\textbf{LOGCFL}$ $\textbf{CFL}$ $\textbf{NL}\subseteq\textbf{LOGCFL}$
$\textbf{NL}\subsetneq\textbf{NP}$ $\textbf{NL}=\textbf{NP}$ $\textbf{NC}^{\textbf{1}}\subsetneq\textbf{PH}$ $\textbf{NP}$ $\textbf{LOGCFL}$ $\textbf{LOGCFL}$

Cependant, ce dernier point laisse toujours la possibilité que SAT ne soit pas dans . En général, je n'ai pas pu trouver grand-chose sur la relation de avec la hiérarchie qui pourrait aider à clarifier le statut épistémique de ma question. $\textbf{CFL}$ $\textbf{CFL}$ $\textbf{NC}$

Remarque (après avoir vu quelques réponses initiales): Je ne m'attends pas à ce que la formule soit sous une forme normale conjonctive (cela ne changera rien à l'essence de la réponse, et généralement les arguments s'appliquent toujours car un CNF est aussi une formule. Mais le prétendre que la version à nombre de variables constant du problème est régulière échoue, car il faut des parenthèses pour la syntaxe.).

Conclusion: Contrairement à ma supposition inspirée de la théorie de la complexité, on peut montrer directement que SAT n'est pas sans contexte. La situation est donc:

On sait que SAT n'est pas sans contexte (en d'autres termes: SAT n'est pas dans ), en supposant que l'on utilise un codage "direct" de formules où les variables propositionnelles sont identifiées par des nombres binaires (et certains d'autres symboles sont utilisés pour les opérateurs et les séparateurs). $\textbf{CFL}$
On ne sait pas si SAT est dans , mais "la plupart des experts pensent" que ce n'est pas le cas, car cela impliquerait . Cela signifie également qu'il est inconnu si d'autres codages "raisonnables" de SAT sont hors contexte (en supposant que nous considérions l'espace de journalisation comme un effort de codage acceptable pour un problème NP-difficile). $\textbf{LOGCFL}$ $\textbf{P}=\textbf{NP}$

Notez que ces deux points n'impliquent pas . Cela peut être montré directement en montrant qu'il y a des langues dans (donc dans ) qui ne sont pas sans contexte (par exemple, ). $\textbf{CFL}\subsetneq\textbf{LOGCFL}$ $\textbf{L}$ $\textbf{LOGCFL}$ $a^nb^nc^n$

cc.complexity-theory circuit-complexity sat context-free mak
la source

Si tel était le cas, alors P = NP.

Ryan

Si SAT était sans contexte, la programmation dynamique (l'algorithme CYK) donnerait un algorithme de temps polynomial pour tester l'appartenance à SAT, donnant P = NP. Même P = NP ne signifierait pas que SAT était sans contexte. Cet encodage de variables semble être plus important que ce que vous lui attribuez. Je n'ai pas travaillé sur les détails mais si vous ajoutiez des "indices" unaires ou binaires aux variables, je pense que vous auriez du mal à distinguer (x et y) de (x et non x) pour des indices suffisamment grands.

AdamF

Vous devez être précis sur la représentation avant de revendiquer des conclusions P = NP. Par exemple, la factorisation d'un nombre N est un temps polynomial dans N (la question intéressante concerne le nombre de bits nécessaires pour écrire N en binaire, ou environ log N).

Aryeh

J'étais au courant de la conclusion P = NP et on ne s'attendait donc pas à ce que la réponse soit "oui" (désolé d'être un peu provocateur dans la façon dont j'ai formulé cela ;-). Je me demandais encore si c'était vraiment connu ou simplement quelque chose que "la plupart des experts croient" (les réponses indiquent maintenant clairement que la première est vraie; j'en sélectionnerai une en temps voulu).

mak

Réponses:

Juste une preuve alternative utilisant un mélange de résultats bien connus.

Supposer que:

les variables sont exprimées avec l'expression régulière $d = (+|-)1(0|1)^*$
et que le langage ( normal ) (sur utilisé pour représenter les formules CNF est: ; il suffit de noter que saisit toutes les formules CNF valides jusqu'à renommer les variables. $\Sigma = \{0,1,+,-,\land,\lor\})$ $S = \{ d^+ (\lor d^+)^*(\land (d^+ (\lor d^+)^*))^* \}$ $S$

Par exemple s'écrit: (l' opérateur a la priorité sur ) . $\varphi = (x_1 \lor x_2) \land -x_3$ $s_{\varphi} = +1 \lor +10 \land -11 \in S$ $\lor$ $\land$

Supposons que st la formule correspondante est satisfiable est CF. $L = \{ s_{\varphi} \in S \, \mid$ $\varphi$ $\}$

Si nous l'intersectons avec le langage régulier: nous obtenons toujours un langage CF. On peut également appliquer l'homomorphisme: , et le langage reste CF. $R = \{ +1^a \land -1^b \land -1^c \mid a,b,c > 0 \}$ $h(+) = \epsilon$ $h(-) = \epsilon$

Mais le langage que nous obtenons est: , car si alors la formule "source" est ce qui n'est pas satisfaisant (de même si ). Mais est une contradiction bien connue du langage non CF . $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
la source

J'ai accepté cette réponse maintenant car il y a toujours un problème ouvert avec l'autre approche (voir commentaires) et j'aime l'argument un peu plus basique. Il pourrait être agréable de souligner que l'argument est spécifique à l'encodage choisi et il est en effet inconnu si l'on pouvait trouver un autre encodage simple (logspace) qui mène à un langage sans contexte.

mak

@mak: Je soupçonne que tout autre encodage "raisonnable" de SAT peut être prouvé non CF avec une technique similaire. Une autre direction intéressante serait peut-être d'étudier si nous pouvons appliquer une sorte de diagonalisation pour obtenir une preuve plus générale: la formule SAT code un calcul qui simule un automate push down sur une entrée donnée et il est satisfaisant si et seulement s'il ne le fait pas '' Je l’accepte. Mais ce n'est qu'une idée floue ...

Marzio De Biasi

Vérifier si une chaîne est dans une langue normale est en P. Supposons que SAT était en Reg. Alors NP = coNP. Soit L dans Reg. Considérez la formule qui est vraie si elle n'est pas en L. Elle est en NP afin qu'elle puisse être exprimée comme une formule SAT. C'est dans la langue si ce n'est pas le cas.

Kaveh

Si le nombre de variables est fini, alors le nombre de conjonctions satisfaisables l'est aussi, donc votre langage SAT est fini (et donc régulier). [Modifier: cette revendication prend la forme CNFSAT.]

Sinon, acceptons de coder des formules telles que par . Nous utiliserons le lemme d' Ogden pour prouver que le langage de toutes les conjonctions satisfaisables n'est pas sans contexte. $(x_{17}\vee \neg x_{21})\wedge (x_{1}\vee x_{2}\vee x_3)$ $(17+\tilde{} 21)(1+2+3)$

Soit la constante de "marquage" dans le lemme d'Ogden, et considérons une formule sat dont la première clause consiste en - c'est-à-dire l'encodage de , où est le nombre décimal composé de ceux. Nous marquons les de et exigeons ensuite que tous les pompages de la décomposition appropriée de (voir la conclusion du lemme d'Ogden) soient également satisfaisables. Mais nous pouvons facilement bloquer cela en exigeant qu'aucune clause contenant , où est une séquence de plus courte que $p$ $w$ $(1^p)$ $(x_N)$ $N$ $p$ $p$ $1^p$ $w$ $x_q$ $q$ $1$ $p$ , soyez satisfiable - par exemple, en vous assurant que chaque autre clause de a une négation de chacun de ces . Cela signifie que échoue à la propriété de "pompage négatif" et nous concluons que le langage n'est pas sans contexte. [Remarque: j'ai ignoré les cas triviaux où le pompage produit des chaînes mal formées.] $w$ $x_q$ $w$

Aryeh
la source

Remarque: Dans mon affirmation selon laquelle pour un nombre fini de variables, le langage est fini, je refuse implicitement de répéter une variable dans une clause ou une clause de manière illimitée plusieurs fois

Aryeh

... Mais je pense que le langage est encore régulier, car on prend la collection finie de formules "essentiellement distinctes" (c'est-à-dire sans répétitions triviales) et on permet ensuite les différentes répétitions.

Aryeh

La réclamation avec régularité ne fonctionne que pour le CNFSAT (j'ai ajouté une précision à ma question).

mak

Même avec des formules arbitraires non CNF à nombre de variables fini, la satisfiabilité (et tout langage qui ne peut pas distinguer deux formules logiquement équivalentes d'ailleurs) est facilement considérée comme hors contexte. Cependant, je ne vois pas la pertinence de cela. La satisfaction des formules dans un nombre fini de variables est un problème trivial qui n'a rien à voir avec la complexité de SAT.

Emil Jeřábek

OK, je vois le problème - je supposais implicitement quepeut être borné en longueur (comme dans le lemme de pompage classique), tout en étant capable de spécifier quelque chose sur son emplacement dans la chaîne. Je pense que l'argument peut être corrigé en refaisant le lemme de pompage à partir de zéro. Nous allons faire de cette première variable une très longue séquence de 1 - suffisamment longue pour qu'un sous-arbre générant une sous-chaîne contiguë de ces 1 soit suffisamment profond pour que le principe du pidgeonhole s'applique.

| x y z |

$|xyz|$

Aryeh