Cours 9 : Rappels, récapitulatif

2-SAT

\[𝜑 = (a∨b) ∧ (¬a∨c)\] \[a∨b ≡ ¬a ⟹ b\]

  digraph {
    rankdir=TB;
    ¬a -> b;
    ¬b -> a;
    a -> c;
    ¬c -> ¬a;
  }

Lemme : $𝜑$ est non satisfiable $⟺$ $∃p_i;$ $p_i$ et $¬p_i$ sont connectés.

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

\[v(l) = true ∧ l⟶^\ast ⟹ v(r) = true\]

---

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

• on devine une variable $p$

  • avec $GAP∈NL$, on vérifie que $p$ et $¬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

\[coGAP≼2-SAT\]

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

\[u \not⟶^\ast v\]

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

on considère $𝜓 ≝ u ∧ 𝜑 ∧ ¬v$

Si une valuation satisfait $𝜓$ et valide $u$, elle valide tous les sommets accessibles depuis $u$, donc $¬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∩V$ (resp. $D∩V$)

• Input : $A_i, ⋯, A_m$ des automates finis

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

  \[L(A_1) ∩ ⋯ ∩ L(A_m)\overset{?}{≠}∅\]

⟶ 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 $∈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$ :

\[ne(A) = ne(A_1)×⋯×ne(A_m) ≤ \vert A_1 \vert × ⋯ × \vert A_m \vert \\ ≤ 2^{\vert A_1 \vert + ⋯ + \vert A_m \vert} ≤ 2^n\]

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

\[r_M : x \mapsto A_1, ⋯, A_n\]

tq

$M$ accepte $x$ ssi $L(A_1)∩⋯∩L(A_1) ≠ ∅$

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

digraph {
  splines=line;
  subgraph cluster_0 {
    label="A_0 : états de M";
    q_0; q_1; q_2; q_f;
  }

  subgraph cluster_1 {
    label="A_1 : lettre en position 1";
    a; b; c; B;
  }

  subgraph cluster_2 {
    label="A_lect : positions de la tête de lecture";
    0; 1; 2; pn;
  }


  q_0 -> q_1[label="r_1, *"];
  q_0 -> q_2[label="r_2, *"];
  q_1 -> q_f;
  q_2 -> q_f;
  a -> a[label="r_i≠1, a"];
  b -> b[label="r_i≠1, b"];
  c -> c[label="r_i≠1, c"];
  B -> B[label="r_i≠1, B"];
  a -> b[label="r_1, a"];
  c -> b[label="r_1, c"];

  0 -> 1[label="r, 0"];
  1 -> 2[label="r'', 1"];
  1 -> 0[label="r', 1"];
}

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∈𝛴 \vert e.e \vert e^\ast \vert e+e' \vert ∅\]

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’$ :

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

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 !