Cours 7 : Complexité : Classe NLOGSPACE, Théorème d’Immerman-Szelepscenyi, Langage d’un automate non déterministe

Classe NLOGSPACE = NL

Il y a pas de problèmes $NL-complets ∈P$

NB : on peut les résoudre efficacement en parallèle.

Problème de l’accessibilité (GAP)

  • Input : $G=(V,E)$ un graphe orienté, $s,t∈V$

  • Question : Existe-t-il un chemin de $s$ à $t$ dans $G$ ?

Lemme : $GAP∈NL$

On utilise le non-déterminisme : on devine un chemin, et on vérifie qu’il va bien de $s$ à $t$.

Attention : on ne peut pas se contenter de partir de $s$ et de deviner une arête, et la suivre, car on pourrait tomber sur un cycle, auquel cas la machine de s’arrêterait pas !

NB : on ne peut pas retenir les sommets déjà visités, si on rester dans NL !

⟶ Solution : on n’a pas besoin de retenir les sommets qu’on a déjà parcourus, mais seulement leur nombre ! (et ça, ça se fait dans NL)

1) Compte |V|=n
2) courant = s
3) Tant que n > 0:
    Si courant = t:
      accepte
    Sinon prendre une arête (u,v)∈E ou rejeter si E=∅ : # non-déterminisme
      Si u≠courant rejette
      Sinon courant = v
      n = n-1
  rejette

NB :

  1. Si on n’a que les arêtes en entrée, et pas les sommets, on initialise $n$ à ce nombre
  2. Si le nom des sommets est donné, et on ne peut pas écrire leurs noms (dans courant) car ils sont trop longs : on utilise des pointeurs vers les sommets.

Lemme : $GAP$ est $NL$-hard.

NMT $ℳ$ utilise $\log n$ espace.

\[r : \begin{cases} 𝛤 ⟶ GAP \\ w \mapsto G_w ≝ (V,E), s_w, t_w∈V \end{cases}\]

tq

\[s_w ⟶^\ast t_w \text{ dans } G_w ⟺ ℳ \text{ accepte } w\]

Idée intuitive :

Les sommets de $G_w$ vont être des quadruplets : état - lettre de gauche - lettre courante - lettre de droite

MAIS : problème : il manque des informations pour l’implication :

\[s_w ⟶^\ast t_w \text{ dans } G_w ⟹ ℳ \text{ accepte } w\]

MIEUX :

les sommets du graphe seront de la forme :

\[q, \$ x \$, i, j\]

  • où :

    • $q∈Q$
    • $x∈M^{≤\log(\vert w \vert)}$
    • $i, j$ : positions (resp.) sur le premier et le deuxième ruban

Transitions de la machine de la forme :

$q, a, a’ \mapsto b, q’, ←, →$ (il y a un ruban d’entrée (en lecture), un ruban de sortie (en écriture))

Dans le graphe, une arête :

\[q, \$x\$, i, j ⟶ q', \$y\$, i', j'\]

est telle que :

  • $w[i]=a$ ($i$-ème lettre de $w$)
  • $x[j]=a’$
  • $y = x[j←b]$
  • $i’=i-1$
  • $j’=j+1$

NB :

  • même si, sur les sommets, on ne voit pas $w$ : les arêtes contiennent l’information relative à $w$
  • on numérote, pour rester dans NL

  • on peut, sans perte de généralité, supposer que $ℳ$ n’a qu’une seule configuration acceptante, correspondant au sommet $t_f$

  • $s_w$ : sommet correspondant à la configuration initiale
  • $t_w = t_f$

⟶ Combien de \(\$ x \\)$ possibles ?

Il y en a : $\vert 𝛤 \vert^{\log n} = n^{\log \vert 𝛤 \vert} ∈ n^{O(1)}$ : on peut les lister (avec un compteur) avec la machine logarithmique (celle qui fait la réduction (pas $ℳ$ !))

La réduction est LOGSPACE en la taille de son input $w$.

Théorème d’Immerman-Szelepscenyi

Théorème d’Immerman-Szelepscenyi :

\[coNL = NL\]

On sait déjà que :

\[NL ⊆ LOG^2 SPACE\]

mais ce résultat est beaucoup moins fort.

Preuve :

Il suffit de résoudre en NL un problème coNL-difficile.

On aura alors

\[coNL ⊆ NL\]

et

\[NL ⊆ coNL\]

le résultat sera acquis.

$coGAP ∈ NL$

Comme GAP est NL-difficile, coGAP est coNL-difficile.

$coGAP ∈ NL$

Étape 1 : Si je sais calculer $\vert Acc(s) \vert$ en NL, alors je sais décider $coGAP$

On note $Acc(S)$ l’ensemble des sommets accessibles depuis $s$.

Si je sais calculer $\vert Acc(s) \vert$ en NL, alors je sais décider $coGAP$.

Algo :

1) Calculer p=|Acc(s)|
2) compteur=0
3) Pour chaque sommet u∈V:
    3.1) Devine si il existe un chemin s⟶* u
        Si c'est le cas :
          on devine un chemin explicite
          compteur +=1
          Si u = t :
            rejette
4) Si compteur=p : accepte
   Sinon : rejette

NB :

  • quand on dit “devine si”, cela correspond à la donnée non déterministe d’un booléen, i.e : on se donne un chemin, on le teste, et on répond (si la réponse est “oui” : on aurait très bien pu tester le bon chemin, mais on a aussi pu tester un mauvais chemin).

Notation :

\[p = |Acc(s)| = p_n \\ p_i = \text{ le nb de sommets accessibles par un chemin de longueur ≤i}\]

Algo pour calculer $p_{i+1}$ à partir de $p_i$ :

1) p_{i+1}=0
2) Pour chaque t'∈V:
    compteur=0, ok =0
    Pour chaque u∈V:
      devine si s⟶≤i u
        si oui, deviner le chemin, le tester
            compteur+=1
        si u,t'∈E:
            ok=1
    Si compteur≠p_i rejette
    Sinon : p_{i+1}+=ok

Cet algo est en espace logarithmique.

  • $p_0 = 1$

et on n’a besoin que de deux trois “cases mémoires”, pour mémoriser :

  • $i$
  • $p_i$
  • $p_{i+1}$

Le résultat est donc acquis.

Langage d’un automate non déterministe

Problème :

  • Input : un NFA $𝒜$
  • Question : $L(𝒜)=∅$ ?

Ce problème dans coNL=NL : car son complémentaire est dans NL : c’est GAP.

NFA ambigu :

si $∃w∈L(𝒜); w$ est accepté par deux chemins différents.

Ex :

NFA ambigu :

digraph {
  rankdir=LR;
  q_0->q_0[label="a,b"];
  q_0->q_1[label="a,b"];
  q_1->⋯[label="a,b"];
  ⋯->q_f[label="a,b"];
  q_f->q_f[label="a,b"];
}

NFA non-ambigu :

digraph {
  rankdir=LR;
  q_0->q_0[label="a,b"];
  q_0->q_1[label="c"];
  q_1->⋯[label="a,b"];
  ⋯->q_f[label="a,b"];
  q_f->q_f[label="a,b"];
}

NB : L’intérêt des NFA non-ambigus, c’est qu’ils sont “plus déterministes” que les NFA ambigus, mais plus “concis” que les DFA (car non-déterministes).

Question : est-ce qu’un NFA est ambigu ou non ?

Si c’est ambigu : Il suffit de deviner un mot qui est accepté par deux chemins différents.

Regarder

\[w=w_1, w_2\]

où

  • $\vert w_1 \vert, \vert w_2 \vert ≤ n^2$

et

\[\begin{cases} I ⟶^{w_1}s⟶^{w_2} F \\ I ⟶^{w_1}s'⟶^{w_2} F \\ s≠s' \end{cases}\]

En fait : ce problème $𝒫$ est même NL-complet

\[GAP ≼ 𝒫\]

Si $G=(V,E), s, t$ est une instance de GAP : on étiquette toutes les arêtes de $G$ par des $a$.

Alors cet automate :

digraph {
  splines=line;
  subgraph cluster_0 {
    label="G";
    s; ⋯; t
  }
  rankdir=LR;
  I->q[label="a"];
  q->F[label="a"];
  q->q[label="a"];
  I->s[label="a"];
  s->⋯[label="a"];
  ⋯->t[label="a"];
  t->F[label="a"];
}

est ambigu ssi il existe un chemin de $s$ à $t$.

Leave a comment