Cours 6 : Complexité : Introduction

Introduction

\[P \overset{?}{ = } NP\]

Attention : dans cette “équation”, NP ne signifie pas

  • “la classe des algorithmes qu’on ne peut pas résoudre en temps non polynomial”,

mais

  • “la classe des algorithmes non déterministes”

Dans les années 80, on disait que :

parmi les algos décidables, ceux “non poly” sont “infaisables en pratique”.

NB : problème $\neq$ programme : pour un même problème, il y a plusieurs algos pour le résoudre a priori.

Complexité d’un problème = complexité du meilleur programme pour le résoudre.

NB :

  • Le cours de complexité, c’est en quelque sorte un cours d’algo, mais on se préoccupe plus des problèmes que des algos en eux-mêmes.

  • Niveau d’abstraction : Calculabilité > Complexité > Algorithmique

On raisonne à un niveau d’abstraction tel qu’on peut donner des réponses à des pbs très difficiles en principe.

Ex :

Problème du circuit Hamiltionien :

  • Instance : un graphe
  • Question : donner un chemin qui passe par tous les sommets une fois et une seule.

NB : pb très important :

  • Anecdote : il existe des entreprises qui vendent des logiciels qui résolvent ce problème

    • ex: optimiser le trajet des éboueurs dans une ville : mais : il fallait constamment recalculer de nouveaux trajets, pour prendre en compte de nouvelles contraintes horaires, travaux, etc…
    • optimiser la coupe d’un robot dans un matériau donné

    En pratique : on arrive à le résoudre dans des situations où les graphes ne sont pas trop, mais on ne connaît pas de solution en temps poly.

Ce pb est NP-complet ⟺ il est “résolu” théoriquement

  • i.e : à condition de faire quelques abstractions :
    • s’intéresser à la complexité asymptotique, dans le pire cas, …
  • Génial : tous les problèmes NP-complets sont équivalents, donc si on sait en résoudre un, on les a tous ⟶ puissance explicative immense, toujours sans savoir si P=NP.

Début du cours

On commence avec quelques définitions.

Problème :

une fonction $A ⟶B$

NB : on suppose qu’on a un codage/une représentation pour ces ensembles.

  • ex : des graphes, des formules logiques, des mots, etc…

    • ex : $f: 𝛴^\ast ⟶ 𝛤^\ast$
Taille de l’instance d’un problème :

La longueur du mot : paramètre par rapport auquel on calcule la complexité.

Représentations d’un graphe (nombre de sommets : $n$, nombre d’arêtes : $m$):

  • avec matrice d’adjacence :

    • $(i,j)=0$ ssi il n’y pas d’arête de $i$ à $j$

    • taille : $n^2$

      • ex : on veut connaître l’existence d’un chemin de $i$ à $j$ (multiplication matricielle)

ou

  • avec une liste d’adjacence :

    • une liste d’arêtes

    • taille : $\log n \times m$

      • $\log n$ : car on représente les numéros des sommets en base 2.

        • NB : dans la pratique, $\log n < 16$, donc c’est quasiment un $O(1)$, mais pour Google par exemple (graphes énormes) : doit être pris en compte

      • ex : on veut pouvoir ajouter des arêtes facilement.

        • Ex: pour les graphes “clairsemés” : ex: graphe des amis sur Facebook

NB : on peut passer facilement d’une représentation à l’autre, donc on ne fera pas de distinction.

Taille d’un nombre d’entiers :

  • $\log n$ : entiers écrits en base $b≥2$

  • $n$ : entiers écrits en base 1.

    • ex : machines de Turing linéairement bornées : n’ont pas le droit d’écrire en dehors de la place allouée par l’entrée (si on donne l’entrée en base 1 : on a plus de place).

Ex :

PGCD $a∧b$ avec l’algorithme d’Euclide :

  • Complexité :

    • en $\log n$, où $n = \max (a, b)$
    • Mais comme la taille de l’entrée est en $\log n$ : l’algo est linéaire.
$O(f)$ :
\[O(f) ≝ \{ g \, \vert \, ∃c>0; ∃n_0; ∀n≥n_0, g(n) ≤ c f(n) \}\]
$𝛺(f)$ :
\[g ∈ 𝛺(f) ⟺ f ∈ O(g)\]
$𝛩(f)$ :
\[𝛩(f) ≝ \{ g \, \vert \, ∃c_1, c_2 >0; ∃n_0; ∀n≥n_0, c_1 f(n) ≤ g(n) ≤ c_2 f(n) \}\]
\[g ∈ 𝛩(f) ⟺ f ∈ O(g) ∧ g ∈ O(f)\]

NB : nos fonctions sont dans $ℕ ⟶ ℕ$, donc pas de valeurs absolues.

Deux mesures de complexité

Le temps :

Le nombre d’opérations élémentaires que le programme effectue.

\[P, i \mapsto Time(P,i) = \text{ nombre d'opérations élémentaires }\]

NB :

  • on pourrait le mesurer en secondes, en nombre de cycles du CPU, etc… mais ainsi, on s’abstrait de la performance matérielle/technologique.
Complexité temporelle en pire cas :
\[P, 𝜋 \mapsto \max_{\vert i \vert ≤ n} \, Time(P,i)\]
$TIME(f)$ :

≝ tous les problèmes solubles par une MT qui répond en temps $≤ f(n)$

  • ex : $TIME(\log), TIME(n^2)$

NB :

  • $TIME(\log)$ : le modèle des MT n’est plus pertinent, car une MT n’a pas une mémoire à accès direct = Random Access Memory

    • ex : recherche dichotomique dans un tableau trié

Au fait : pourquoi

$TIME(f) ≝ $ tous les problèmes solubles par une MT qui répondent en temps $≤ f(n)$

et pas

$TIME(f) ≝ $ tous les problèmes solubles par une MT qui répondent en temps $O(f)$ ?

CAR :

Th : \(∀c>0, TIME(f) ⊆ TIME(cf + n + 2)\)

NB :

  • $n+2$ : lecture de l’entrée (cf. plus bas)
  • il faut qu’on puisse calculer $f$ en temps $O(f)$

Comment fait-on, par exemple, avec $c=\frac 1 2$ ?

Idée de Dém :

  1. On a une MT qui lit les lettres deux par deux : on change l’alphabet, en considérant maintenant les couples de lettres.

    • pour cela, on lit l’entrée (d’où le $n$, dans le théorème).

  2. On réécrit la table de transition pour que cette fasse exactement la même chose que la première.

Espace :
\[P, i \mapsto \text{ nb de cases utilisées sur le ruban de travail}\]
  • NB : s’il y a plusieurs rubans de travail : on prend le max.
$SPACE(f)$ :

≝ tous les problèmes solubles par une MT qui utilise un espace $≤ f(n)$

Th : \(∀c>0, SPACE(f) ⊆ SPACE(cf)\)

Dém :

même astuce qu’avant, sauf que lire l’entrée prend du temps et pas de l’espace.

NB : ces deux mesures (espace et temps) sont très pertinentes à échelle humaine : taille de la mémoire de l’ordinateur, et temps dont on dispose.

Ex :

  1. Si on sait que notre algo de graphe est en temps $O(n^3)$,

  • on peut traiter des graphes de taille 1000

    • ex: circuit dans une ville

  • mais pas de taille $10^6$

    • ex: graphe des amis de Facebook

NB : un ordi fait environ $10^9$ opérations par seconde.

  1. Si on sait que notre algo de graphe est dans $SPACE(n^3)$ :
  • on ne dépassera pas le téraoctet

Ex : on peut laisser tourner un programme tout une semaine avec de grosses instances (plusieurs milliers) s’il est en temps $O(n^3)$, mais doit être dans $SPACE(\log n)$ par exemple, car :

  • le temps s’augmenter de manière “linéaire” en attendant suffisamment longtemps
  • pas l’espace : fixé par l’ordinateur.

NB :

  • opérations élémentaire : Exs :

    • le nombre d’allers-retours dans un protocole réseau
    • overlays : on libère dynamiquement la mémoire en se débarrassant des parties du code d’un programme dont on n’a plus besoin ⟶ nombre d’overlays
    • ordinateurs quantiques : encore d’autres opérations élémentaires.

Une dimension supplémentaire : le non-déterminisme

$NTIME(f)$ :

≝ tous les problèmes solubles par une MT non déterministe qui répond en temps $≤ f(n)$

Temps de réponse : le max des temps possibles.

NB : on essaye d’éviter le non-déterminisme.

Mais dans la nature : il existe des programmes non-déterministes :

Exs :

  • tri bulle, où supprime une inversion au hasard
  • tri rapide : choix du pivot

Le fait de pouvoir écrire des algos non déterministes ⟶ correction de l’algo beaucoup plus simple.

$SPACE(f)$ :

≝ tous les problèmes solubles par une MT non déterministe qui utilise un espace $≤ f(n)$

Espace utilisé : le maximum, pour les calculs possibles.

NB : les machines déterministes sont des cas particulier de machines non-déterministes.

Th : \(∀c>0, NTIME(f) ⊆ NTIME(cf + n + 2)\)

\[∀c>0, SPACE(f) ⊆ SPACE(cf)\]

Propriété : \(TIME(f) ⊆ SPACE(f)\)

Dém : trivial, car pour écrire $f(n)$ lettres sur le ruban, il faut $f(n)$ opérations.

Propriétés :

\[TIME(f) ⊆ NTIME(f)\] \[SPACE(f) ⊆ NSPACE(f)\]

Dém : trivial, car les machines déterministes sont des cas particulier de machines non-déterministes.

Classes polynomiales

\[P ≝ \bigcup\limits_{c∈ℕ} TIME(n^c) ≝ TIME(n^{O(1)})\] \[PSPACE ≝ \bigcup\limits_{c∈ℕ} SPACE(n^c) ≝ SPACE(n^{O(1)})\]

Idem pour $NP$, $NPSPACE$, …

Classes exponentielles

\[EXPTIME ≝ \bigcup\limits_{c∈ℕ} TIME(2^{n^c}) ≝ TIME(2^{n^{O(1)}})\] \[(N)LOGSPACE ≝ SPACE(\log n)\]

Inclusions de classes

\[\begin{matrix} LOGSPACE &⊆ NLOGSPACE &⊆ PSPACE &= NPSPACE \\ P &⊆ NP &⊆ EXPTIME \\ \\ NLOGSPACE &⊆ P &⊆ PSPACE \\ EXPTIME &⊆ NPSPACE \end{matrix}\]
\[L⊆A^\ast\] \[L∈coNP ⟺ A^\ast\backslash L ∈ NP\]

NB : cette notion de “co” est inutile pour les classes déterministes :

\[coPTIME = PTIME\]

quitte à inverser les réponses.

NB 2 : on ne peut pas simplement inverser les réponses pour les MT non déterministes :

NON(il existe un chemin acceptant) ⟺ tout chemin n’est pas acceptant

\[NP ⊆ PSPACE\]

⟶ on simule des branches par “backtracking” avec une pile de taille polynomiale.

⟶ l’exploration de l’arbre prend un temps exponentiel, mais est polynomial en espace.

Réduction du problème $𝒫⊆A^\ast$ au problème $𝒫’⊆A^\ast$ :

$𝒫 ≤ 𝒫’$

⟺ ∃ une réduction de $𝒫$ à $𝒫’$

⟺ $∃ r : A^\ast ⟶ A^\ast$ calculable tq $∀ n, r(n)∈𝒫’ ⟺ n ∈ 𝒫$

Si $𝒫 ≤ 𝒫’$ et

  • $𝒫$ indécidable, alors $𝒫’$ indécidable
  • $𝒫’$ décidable, alors $𝒫$ décidable

On va adapter la définition pour les classes de complexité :

si on veut pour la classe de complexité $PTIME$ : $r$ sera pris en espace logarithmique $LOGSPACE$, par exemple.

NB :

  • Réduction trop restreinte : complique énormément les choses
  • Réduction trop forte : mélange des choses qu’on ne voudrait pas : car $r$ pourrait être aussi, voire plus compliquée que le problème lui-même (si elle est dans la même classe que $𝒫$)

$𝒞$ une classe de problèmes :

Problème $𝒫$ est $𝒞$-hard :

$∀𝒫’ ∈ 𝒞, 𝒫’ \overset{LOGSPACE}{≤} 𝒫$

Attention : la composition de réductions en LOGSPACE n’est pas trivialement en LOGSPACE !

en effet:

la sortie d’une réduction en LOGSPACE n’est pas forcément logarithmique en espace !

ruban A_entrée x ⋯ x
ruban A_travail LOG
ruban A_sortie y ⋯ y
ruban B_entrée y ⋯ y
ruban B_travail LOG
ruban B_sortie z ⋯ z

entre A_entrée et B_sortie : on utilise un espace “y ⋯ y” non maîtrisé.

En fait : LOGSPACE est bien stable par composition, mais c’est un théorème.

Idée de la preuve :

lire le i-ème caractère de A_sortie en réexécutant A depuis le début jusqu’au i-ième caractère de sortie à chaque fois.

Problème $𝒫$ est $𝒞$-complet :

$𝒫$ est $𝒞$-difficile et $𝒫∈𝒞$

NB :

  1. En fait, c’est le problème “le plus difficile” de $𝒞$

  2. Dans la terminologie moderne, la réduction est supposée en LOGSPACE

    • avant : “$𝒫$ est $PTIME$-complet pour $𝒞$” : pour dire que $𝒫$ est $𝒞$-complet avec des réductions en $PTIME$

À quoi cela sert-il de répertorier des problèmes NP-complets ?

ex :

Thm : Circuit Hamiltionien est NP-complet

cela répond d’une façon définitive à la question “peut-on faire mieux ?”, si on a un algo pour le résoudre de la classe NP.

NB :

  • chaque classe de problème a des heuristiques qui lui sont propres

    • par exemple, en pratique : comment éviter les cas pires ?

Souvent :

pour montrer que notre problème est NP-hard :

  • on peut faire une preuve “from scratch”

  • on peut réduire un problème NP-dur connu à ce problème

    • on essaye d’avoir la réduction la plus simple possible

Ex : Livre de Gareth Johnson répertoriant des centaines de problèmes NP-durs classés par “thèmes” (graphes, etc…)

Pb : SAT = Satisfiabilité booléenne d’une formule propositionnelle (logique d’ordre 0)

  • Input : Formule propositionnelle

    • propositions $p_1, ⋯, p_n$ vraies ou fausses
    • conjonctions, disjonctions, négations, etc… des ces propositions

  • Question : est-ce que la formule est statisfaisable ? (i.e : existe-t-il une interprétation $𝜇$ des propositions telle que la formule soit vraie.)

SAT ∈ NP

Pourquoi dans NP ?

La MT qui résout SAT :

  • teste les interprétations possibles des $p_i$ de façon non déterministe
  • puis évalue la formule

NB : si on voulait le faire de façon déterministe, ça prendrait un temps exponentiel (pour tester les $2^n$ interprétations possibles).

SAT est NP-difficile

Soit $𝒫∈NP$.

Montrons que $𝒫≤SAT$.

Il existe une MT $M_𝒫$ qui résout $𝒫$ en temps $p(n)$.

On réduire $𝒫$ à SAT.

Sans perte de généralité : la machine $M_𝒫$ utilise le ruban d’entrée comme ruban de travail.

\[r : \begin{cases} A^\ast ⟶ Form\_Bool \\ w \mapsto r(w) \end{cases}\]

Ruban :

    $0$ $1$   ⋯   $n$     $p(n)$
$l=1$ $q_{init}$ $$$ $w_1$   ⋯   $w_n$ $b$ $b$  

  • $a_i^j$, $a∈𝛤$

    • la lettre qu’il y a en $(i, j)$ dans le tableau précédent

  • $q^j$, $q∈Q$

    • à la ligne $j$ : on est à l’état $q$

  • $l_i^j$

    • à la ligne $j$, la tête de lecture est à la colonne $i$

Formules :

  • $F_1$ : il n’y a pas deux lettres $a, b$ telles que $a_i^j$ et $b_i^j$ sont simultanément vraies
  • $F_2$ : Pour tous $i, j$ : il existe une lettre $a$ telle que $a_i^j$

Idem pour les états, puis les têtes de lectures.

On a un ensemble de formules propositionnelles qui caractérise le tableau précédent, qui est lui-même une exécution de la MT sur sur l’entrée $w$

Puis :

  • on peut trouver une formule disant :

“le tableau a pour première ligne la ligne la ligne :”

|$l=1$|$q_{init}$|$$$|$w_1$| | ⋯ ||$w_n$|$b$|$b$|| |-|-|-|-| -| - |-|-|-|-|-|

  • on peut trouver une formule disant : à la ligne $j$, si la tête de lecture n’est pas à la colonne $i$ et si $a_i^j$, alors $a_i^{j+1}$
  • en utilisant la table de transition de la MT, on exprime par une formule que $q^j ∧ l_i^j ∧ a_i^j ⟹$ une des lignes suivantes possibles.

Ainsi, MT résout $𝒫$ ssi les formules précédentes sont satisfaisables.

En fait :

même 3-SAT est NP-complet

en effet : on se ramène à 3 variables en renommant des sous-formules comme de nouvelles variables.

NB : pour des conjonctions, on a besoin d’au moins trois variables.

Si $p = x_1 ∧ x_2$,

\[x_1 ∧ x_2 ⟹ p \\ \lnot x_1 ⟹ p \\ \lnot x_2 ⟹ p\]

Circuit Hamiltonien NP-dur

  • NP : clair
  • NP-dur : on réduit 3-SAT à ce problème.

Théorème de Savitch

Outil utile :

Si $G = (V, E)$, $s, t∈ V$ : existe-t-il un chemin de $s$ à $t$ ?

Alogirthmes pour le faire :

  • Djikstra (linéaire)
  • FLoyd Warshall (en $O(n^3)$)

MAIS : on peut le faire en $O(\log^2(\vert V\vert))$, avec le paradigme “diviser pour régner” :

Soit 1≤ l≤ n-1

Pour tous les sommets w à une distance l/2 de s :
  chercher s'il y a un chemin (s, w, l/2) et un chemin (w, t, l/2)

Complexité spatiale :

  • Spatiale : une pile d’au plus $\log n$ blocs de taille au plus $\log n$ ⟶ $\log^2 (n)$

  • Temporelle : $(2n)^{\log n}$

    • pas polynomiale

Th de Savitch :
\(NSPACE(f) ⊆ SPACE(f^2)\)

Soit $M, w$, avec

  • des configurations de taille $f(n)$, où $n = \vert w\vert$

L’ensemble des configs forme les sommets d’un graphe : on passe de l’une à l’autre par un temps de calcul.

Question : existe-t-il un chemin de taille au plus $f(n)$ de la configuration initiale à “la” configuration finale (sans perte de généralité : on peut considérer qu’il y a une seule config qui accepte, quitte à “rediriger” toutes les configs acceptantes vers une unique config finale).

Nombre de configurations :

  • un état de contrôle
  • position de la tête de lecture
  • mot sur le ruban

⟶ $\vert Q \vert × f(n) × 𝛤^{f(n)}$

On utilise l’algo précédent :

Corollaire :

\[NPSPACE ⊆ PSPACE\]

et comme on avait déjà l’inclusion inverse, on a :

\[NPSPACE = PSPACE\]

Moralité :

  • le non déterminisme ne “coûte rien” ⟶ ne pas s’en priver dans les preuves, par exemple.

De même :

  • \[NEXPSPACE = EXPSPACE\]

Mais c’est moins intéressant en l’occurrence, car on peut déjà déterminiser en temps exponentiel (c.f déterminisation des automates).

  • \[LOGSPACE ⊆ NLOGSPACE ⊆ {LOG}^2SPACE\]

NB : En logique, $PSPACE$ est une classe très importante : porlbèmes difficiles à résoudre, mais pas impossibles.

Problème QBF

QBF :

Quantified Boolean Formula

Ex : $∀p_1, ∃p_2, (p_1 ∧ p_2 ∨ ¬ p_3)$

NB :

SAT concernait les formules propositionnelles : on cherchait des modèles (valuations) satifaisant une formule donnée.

\[v: Prop ⟶ \lbrace T, F\rbrace, v \vDash 𝜑\]

Sémantique de satisfaisbilité maintenant :

  • \[v(∃p 𝜑_1) = v(𝜑_1[p/T]) ∨ v(𝜑_1[p/F])\]
  • \[v(∀p 𝜑_1) = v(𝜑_1[p/T]) ∧ v(𝜑_1[p/F])\]
Formule close :

Toutes les propositions sont sous quantificateurs

NB :

  • Dans SAT, tout était quantifié existentiellement : sans quantificateur ⟺ il existe un littéral …
  • Mais les variables libres ne sont pas forcément quantifiées existentiellement : ça dépend du contexte.
Problème QBF :

étant donnée une formule close : est-elle vraie ?

Lemme : \(QBF ∈ PSPACE\)

  • Attention : en éliminant les quantificateurs, on rend l’expression de la formule exponentielle en espace : pas bon !

On va supposer que tous les quantificateurs sont au début : forme prénexe :

  • $¬ ∀p, 𝜑 ≡ ∃p, ¬𝜑$
  • $(∃p, 𝜑) ∧ 𝜓 ≡ ∃p’ (𝜑[p/p’] ∧ 𝜓)$

Comment fait-on ?

On garde une pile initialisée à

$p_1$ $p_2$ ⋯ $p_{n-2}$ $p_{n-1}$ $p_n$
T T ⋯ T T T

puis, on essaye toutes les valeurs possibles, récursivement, et on fait remonter le résultat (éventuelllement avec un autre tableau) :

⇓

$p_1$ $p_2$ ⋯ $p_{n-2}$ $p_{n-1}$ $p_n$
T T ⋯ T T F

⇓

⋯

LEMME : $QBF$ est $PSPACE-hard$

Soit $L⊆ PSPACE$.

Montrons que $L≼ QBF$.

Construisons une réduction

\[r_L : w \mapsto 𝜑_w∈QBF\]

tq

\[w∈L ⟺ 𝜑_w \text{ est vraie}\]

Plan :

Taille du ruban = $p(n)$

Ruban d’entrée = ruban de travail.

état\tête de lecture $\downarrow$ ⋯        
$q_{init}$ $w_1$ ⋯ $w_n$ $b$ ⋯ $b$
    $\downarrow$ ⋯      
$q_{1}$ $a$ ⋯ $w_n$ $b$ ⋯ $b$

On a des formules :

1.

  • la tête de lecture est en $i$
  • la lettre en position $i$ est $a$
  • l’état de contrôle
  1. Un formule $𝛩(𝛾) ≡ 𝛾 \text{ code bien une configuration}$, qui vérifie que :
  • la tête de lecture en un et un seul indice $i$
  • la tête de lecture est sur une et une seule lettre courante
  • $𝛾$ est en un et un seul état

Cette formule est polynomiale en espace.

  1. Une formule $𝜑_1(𝛾_1, 𝛾_2)$ qui vérifie que :
  • $𝛾_1$ et $𝛾_2$ sont des configurations

  • on peut passer de $𝛾_1$ à $𝛾_2$ en au plus une étape :

    • toutes les lettres sauf la lettre sous la tête de lecture sont inchangées
    • la table de transition de la machine permet de passer de la première à la seconde
  1. Une formule $𝜑_2(𝛾_1, 𝛾_2)$ qui vérifie que :
  • $𝛾_1$ et $𝛾_2$ sont des configurations

  • on peut passer de $𝛾_1$ à $𝛾_2$ en au plus deux étapes : i.e

    • il existe une configuration $𝛾’$ telle que :

      • $𝜑_1(𝛾_1, 𝛾’) ∧ 𝜑_1(𝛾’, 𝛾_2)$
  1. Idem pour $𝜑_k(𝛾_1, 𝛾_2)$

On a donc des formules $𝜑_1(𝛾_1, 𝛾_2), ⋯, 𝜑_{\log(2^{p(n)})}(𝛾_1, 𝛾_2)$ (car on double la taille à chaque fois)

MAIS : problème, à chaque fois, on double la taille de la formule $𝜑$ ⟶ ça ne va pas, la taille de la dernière formule est exponentielle !

Astuce : On peut utiliser des quantificateurs pour passer de $𝜑_k$ à $𝜑_{k+1}$

NB : QBF correspond aux machines alternantes (cf. TD) en temps polynomial.

Cas particulier aussi PSPACE-complet :

Problème QSAT :

Des quantificateurs au début, puis des formules 3CNF

Problème : Universalité des langages réguliers

  • Input : Un expression régulière $E$, un alphabet $A$
  • Output : est-ce que \(L(E) = A^\ast\)

Problème décidable : construction d’un automate qui reconnaît $E$, d’un automate qui reconnaît tout, puis : différence symétrique.

Lemme : $UNIV ∈ PSPACE$

1) On construit un automate $A_E = (Q, 𝛴, ⋯)$ non dét. de taille $O(E)$

2) L’automate déterministe a comme ensemble d’états $𝒫(Q)$

3) Si $A_E$ n’est pas universel, $∃w∉L(A_E), \vert w \vert ≤ 2^{\vert Q \vert}$

Question : l’existence d’un chemin de l’état initial à l’état final de taille $2^{\vert Q \vert}$ au plus.

Lemme : $UNIV$ est $PSPACE-dur$

On préfère réduire les machines de Turing plutôt que les machines alternantes (QBF) : on réduit un problème de $PSPACE$ quelconque à ce problème.

$L, M, p$

Soit $L∈ PSPACE$.

Montrons que $L≼ QBF$.

Construisons une réduction

\[r_L : w \mapsto E_w, 𝛴_w∈UNIV\]

tq

  • $r_L$ est Logspace-calculable
  • \[w\not∈L ⟺ L(E_w) = 𝛴_w^\ast\]

NB : on doit mettre dans le même sac les mots qui ne sont pas des calculs avec les mots qui acceptent OU n’acceptent pas ⟶ on préfère reconnaître $L^c$ pour pouvoir mettre facilement dans le même sac les mots qui ne sont pas des calculs avec les mots qui n’acceptent pas.

On considère la machine reconnaissant $L^c$ (on peut inverser les états acceptans/non acceptants en espace polynomial).

Plan :

Taille du ruban = $p(n)$

Ruban d’entrée = ruban de travail.

ruban   ⋯        
  $(w_1,q_{init})$ ⋯ $w_n$ $b$ ⋯ $b$
  $a$ $(w_2,q_{1})$ ⋯ $w_n$ ⋯ $b$

On code le chemin

\[𝛾_1 ⟶ ⋯ ⟶ 𝛾_n\]

par

\[rub(𝛾_1) \# ⋯ \# rub(𝛾_n)\]

Donc \(𝛴_w = 𝛤 ∪ 𝛤×Q ∪ \#\)

On va décrire les mots qui ne codent pas des calculs acceptants de $M$ sur $w$.

Si $c$ n’est pas de la forme $rub(𝛾_1) # ⋯ # rub(𝛾_n)$ :

  • OU BIEN : $c$ ne commence pas par $#$
  • OU BIEN : ne termine pas par $#$
  • OU BIEN : deux $#$ sont séparés par strictement moins, ou strictement plus que $p(n)$ lettres différentes de $#$
  • OU BIEN : contient deux états, ou 0 état

etc… : on peut donc vérifier que $c$ est de la bonne forme syntaxique ou non.

Maintenant :

  • Énumérons les configurations $𝛾’$ qui ne peuvent pas succéder pas à $𝛾$ :

    • une lettre (non couplée à un état) a été modifiée en une autre lettre non couplée à un état.
    • en considérant la fenêtre de longueur 3 centrée en $(a’, q’)$, cette même fenêtre a été modifiée illégalement (d’après la table de transition) dans $𝛾’$

On a ainsi une expression régulière reconnaissant tous les mots qui ne codent pas mot correspondant à un chemin acceptant.

Le langage est universel ssi il n’existe pas de mot acceptant ssi $w∉L$.

Leave a comment