2-SAT

Lemme : $𝜑$ est non satisfiable $⟺$ $\exists p_i;$ $p_i$ et $\neg p_i$ sont connectés.

Si $v:Prop⟶Bool$ une valuation qui satisfait $𝜑$ :

En fait : on a même mieux que polynomial :

• on devine une variable $p$

  • avec $GAP\in NL$, on vérifie que $p$ et $\neg p$ sont dans la même cfc ou non
  • ils le sont ssi $𝜑$ est non satisfiable

Donc le problème est dans $coNL=NL$.

NB :

Prop : 2-SAT est NL-complet.

Preuve :

On réduit

Étant donné $G=(V,E)$, est-il vrai, pour $u,v\in V$, que :

Le graphe donne une formule $𝜑$ sur contruite sur le modèle précédent, puis :

on considère $𝜓\stackrel{\scriptscriptstyle\mathrm{def}}{=}u\wedge 𝜑\wedge \neg v$

Si une valuation satisfait $𝜓$ et valide $u$, elle valide tous les sommets accessibles depuis $u$, donc $\neg v$ ssi $v$ est accessible depuis $u$.

Problème utile aux chercheurs : intersection de langages réguliers

En combinant des langages réguliers, on peut dire des choses compliquées

Il y a deux variantes du problème : avec des automates déterministes (resp. non déterministes) : $N\cap V$ (resp. $D\cap V$)

• Input : $A_i,\cdots ,A_m$ des automates finis

• Question : Est-ce qu’il existe un mot dans l’intersection des langages ?

  $$L(A_1)\cap \cdots \cap L(A_m)\stackrel{?}{\ne }\varnothing$$

⟶ Problème décidable :

• on peut considérer l’automate produit, qui reconnaît l’intersection des langages.

• le problème est dans $EXPTIME$ : on se ramène à un problème d’accessibilité dans un graphe.

  MAIS : accessibilité dans un graphe $\in NL$, donc en s’arrangeant un peu, on pourrait le faire tomber dans $NPSPACE=PSPACE$

NB : les états de l’automate produit sont des $m$-uplets d’états des $A_i$ :

NB : comme $m$ n’est pas fixé (c’est une variable) : la majoration est exponentielle. Si on avait eu $m=2$, ça aurait été quadratique.

On devine un mot de longueur $l\le 2^n$.

On ne peut pas mémoriser le mot en entier : il est trop long.

On teste la reconnaissabilité du mot “à la volée” :

• on part de tous les états initiaux, on initialise un compteur à $l$
• on devine une lettre $a_1$, et on obtient l’état produit ($m$-uplet d’états), puis on décrémente $l$.
• on continue jusqu’à ce que le compteur atteigne $0$ : puis on vérifie on est dans un état produit acceptant ou non.

Ce problème est dans $PSPACE$.

Il est même $PSPACE-difficile$.

⟶ On peut penser réduire le problème de l’universalité d’un automate non déterministe (est-ce qu’il reconnaît tous les mots ?), qui est $PSPACE-complet$.

NB :

• mais difficulté : ce problème n’est pas universel, donc pas forcément le bon problème à réduire.

$M$ une MT déterministe en espace $p(n)$.

tq

$M$ accepte $x$ ssi $L(A_1)\cap \cdots \cap L(A_1)\ne \varnothing$

Alphabet des $A_i$ : paires de règle (de la table de transition) et de position (de la tête de lecture sur le ruban).

Connaissant un mot de telles paires $(r,i)$, on peut dresser un tableau d’exécution de $M$ sur $x$.

Réciproquement : on construit des automates dont le produit ne reconnaît que les exécutions acceptantes de la machine sur $x$.

Quels automates sont non déterministes si la machine l’est ?

Une MT ND peut avoir plusieurs états de départ dans $A_0$ (pas forcément $q_0$) : seule chose qui diffère.

Choses utiles à savoir

Expressions régulières :

$$e:=a\in 𝛴|e.e|e^{\ast }|e+e^{\prime }|\varnothing$$

Est-ce que le langage dénoté par $e$ est vide ou non ?

⟶ c’est LOGSPACE : formule booléenne.

Expressions régulières étendues :

stables par intersection, en plus

On ne peut plus tester la vacuité en LOGSPACE car le problème est maintenant PSPACE-complet !

• C’est PSPACE-dur car plus général que le problème précédent
• plus difficile que c’est dans PSPACE puisqu’on ne peut plus mémoriser d’état

Le shuffle de deux langages réguliers $L$ et $L^{\prime }$ :

c’est le langage formé de tous les mots dont les lettres appartiennent à un mot de $L$ ou à un autre mot de $L^{\prime }$

ex :

shuffle de $a^{\ast }$ et $b^{\ast }$ : c’est $(a+b{)}^{\ast }$

Expressions régulière stables par puissance :

c’est PSPACE, encore une fois

Expressions régulière stables par négation :

l’universalité avec la négation est non élémentaire :

“tower-complete” :

espace/temps pas borné par un polynôme NI une exponentielle à une puissance fixée !