TD7 : Complexité : Accélération linéaire, Réductions LOGSPACE et Machines alternantes

Version PDF

Réductions LOGSPACE

Q 2.

Mq toute MT déterministe qui calcule une réduction en espace logarithmique s’arrête après un nombre d’étapes polynomial.

Si une fonction est logarithmique en espace, le nombre d’étapes est polynomial.

Attention : LOGSPACE n’est pas clos de $k$ rubans à 1 ruban (il y a un passage au carré ⟶ on a du $log^2(n)$), donc travailler sur $k$ rubans ou 1 ruban n’est pas équivalent.

Machine à $k$ rubans.

Nb de configurations :

\[N = \vert Q \vert \times (\vert 𝛴 \vert^{\log n})^k \times \lceil \log(n) \rceil^k \times n\]

(états, contenus des $k$ rubans, position des têtes de lecture, taille de l’entrée)

Or : toute exécution de la MT qui s’arrête ne peut pas passer par deux configurations identiques :

donc ce nombre est majoré par $N$, et est donc polynomial.

Q 3.

Soient $h_1 = L_1 ⟶ L_2$ et $h_2 : L_2 ⟶ L_3$ deux réductions calculables en espace logarithmique par des machine déterministes.

Mq la réduction $h_1 \circ h_2$ peut être calculée en espace logarithmique.

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

en effet:

$A$ la MT qui calcule $h_1$, $B$ celle qui calcule $h_2$.

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” polynomial (cf. Q2).

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

Idée de la preuve :

Pour lire le i-ème caractère de A_sortie :

on réexécute A depuis le début jusqu’au i-ième caractère, qu’on écrit seul sur le ruban de sortie à chaque fois.

Détails :

  • Init : $c=0$

    Puis : on simule $M_{h_1}$ mais on incrémente $c$ si $M_{h_1}$ écrit sur la sortie

  • et quand $c=i$, on finit en écrivant ce que $M_{h_1}$ voulait écrire donc $h_1(x)[i]$
  • Enfin, $M_{h_2\circ h_1}$ : quand on a besoin d’accéder à $h_1(x)[i]$, on procède comme précédemment.

Q 4

1.

Lemme : \(ATIME(f(n)) ≤ SPACE(f^2(n))\)

$f$ constructible :

Si il existe $M_f$ calculant $f$ en temps $O(f)$

$M∈ATIME(f(n))$ :

on procède de même que pour

\[NP ⊆ PSPACE\]

⟶ on simule des branches par “backtracking” avec une pile de taille $f(n)$.

⟶ l’exploration de l’arbre prend un temps exponentiel, mais vaut $f(n)$ en espace.

def exploration(config_initiale, Q, delta, lambda_value, f_n):
    tableau = { q:lambda_value(q) for q in Q }
    pile = [config_initiale]
    while pile:
        config_courante = pile.pop()
        for config in delta[config_initiale]:
            pile.append(config)
            if tableau[q] == 'top':
                tableau[config_courante] = tableau[config_courante] lambda_value(config_courante) true
            elif tableau[q] == 'bot':
                tableau[config_courante] = tableau[config_courante] lambda_value(config_courante) false
            else:
                if lambda_value(config_courante) == 'or':
                    tableau[config_courante] = false
                else:
                    tableau[config_courante] = true
    return tableau[config_initiale]

2.

Soit $M$ une ATM calculant en ASPACE($f(n)$).

Pour tout $x$, l’arbre d’exécutions contient au plus $c^{f(n)}$ configurations (pour $c$ constant).

  1. On calcule toutes les configurations de taille $f(n)$.

    $𝛾_1, \bot # ⋯ # 𝛾_m, \bot$ ($m≤c^{f(n)}$)

    Avec $l_i ∈ \lbrace 1, 0, \bot \rbrace$

    On prendra $𝛾_1 = 𝛾_i(x)$

     for i = 0 to m:
     copie gamma_i sur une seconde bande
             gamma_i \# l_i' =
                     0 si lambda(gamma_i) = or
                     1 si lambda(gamma_i) = and
                     0 si lambda(gamma_i) = bot
                     1 si lambda(gamma_i) = top
     for j=0 to m:
         f(gamma_i  -> gamma_j) then
             l_i' <- l_i' lambda(gamma_i) l_j

     Update  la liste l_j <- l_j'
     Retourner l_1

    Il y a au plus $\vert Q \vert \times (\vert 𝛴 \vert^{f(n)})^k \times \max(n, f(n))^k$

3.

  • $∃$ un chemin de $𝛾_0$ à Accept

Pour $c=2$ :

Soit $m=2^{f(n)}$ une borne sur la longueur des chemins.

On suppose sans perte de généralité que $M$ calcule en temps exactement $m$.

\[Reach(2^0, x, y) ⟺ x⟶y \\ Reach(2^{𝛼+1},x,y) ⟺ ∃z (de taille $f(n)$); (Reach(2^𝛼, x, z) ∧ Reach(2^𝛼, z, y))\]

On a $f(n)$ appels récursifs, et à chaque appel, on devine une configuration de taille $f(n)$.

Complexité : $O(f(n)^2)$

Pour $c=2^𝛽$ :

$M$ accepte $x$ ⟺ $Reach((2^𝛽)^{f(n)}, 𝛾_0, Accept)$

NB :

\[AP ⊆ PSPACE \\ NPSPACE ⊆ AP\]

donc \(AP = PSPACE\)

et on a aussi :

\[APSPACE = EXPTIME\]

Réductions

EX 1

Montrer que INDEPENDENT SET est $NP$-complet.

  • Entrée : un graphe $G$ non orienté.
  • Question : $G$ a-t-il un ensemble indépendant de cardinal supérieur à $m$ ?
  1. Le problème est $NP$ : On vérife en temps polynomial q’un ensemble de sommets est une clique dans le “complémentaire du graphe” $G^c$ (i.e : le graphe obtenu à partir de $G$ en remplaçant les 1 de la matrice d’adjacence par des 0, et les 0 par des 1).
Algorithme :
    S = ∅

    Pour v ∈ V:
        S = S || S = S ∪ {v}
        # choix non déterministe

    Pour v∈V, v'∈V, v≠v':
        Si (v, v')∈E:
            Echec

    Si |S|<m :
        echec
  1. Le problème est $NP$-complet :

Réduction de SAT à ce problème $𝒫_1$ :

\[SAT ≼ 𝒫_1\]

Idée de la preuve :

Pour une conjonction $f$ de $m$ clauses satsifiable :

\[f ≝ \bigwedge_{i=1}^m \bigvee_{j=1}^n a_{i, j}\] \[C_1 = a_{1,1} ∨ a_{1,2} ∨ a_{1,3} ∨ a_{1,4}\] \[C_2 = \lnot a_{2,1} ∨ a_{2,3} ∨ a_{2,5}\]

Proposition : $f$ est satisfiable $⟺$ il existe un ensemble indépendant $S$ de card supérieur à $m$.

L’idée est qu’on va mettre dans une même clique les variables d’une même clause donnée (pour la CS), et qu’on va relier deux sommets s’ils la négation et l’affirmation d’une même variable (pour interdire le choix de $x$ et $\lnot x$).

  • si la formule est vraie, alors chaque clause $i$ contient une variable $a_{i,j}$ vraie : l’ensemble des sommets correspondants est indépendant (et il est de taille $m$).
  • si on a un ensemble indépendant $\lbrace v_1, ⋯, v_n \rbrace$ de taille supérieure à $m$, alors nécessairement les $v_i$ sont dans des cliques différentes et deux $v_i$ ne sont pas l’affirmation et la négation d’une même variable : chaque $v_i$ appartient à une clause $C_i$, qui est donc vraie, et $f$ est vraie.
graph {
		a_11 -- a_21;
		a_11 -- a_31;
		a_11 -- a_41;
		a_21 -- a_31;
		a_21 -- a_41;
		a_31 -- a_41;
        ￢a_12 -- a_11;
        ￢a_12 -- a_32;
		￢a_12 -- a_52;
		a_32 -- a_52;
	}
  • ⟸ :

La réduction est en LOGSPACE :

  • construire les sommets un parcours des littéraux de la formule
  • Pour les arêtes : deux boucles for imbriquées

EX 2

$C$ est un recouvrement ssi $C^c$ est indépendant.

NB : la réduction est encore en LOGSPACE.

EX 3

$C$ est une clique ssi $C$ est un ensemble indépendant dans le graphe complémentaire.

EX 4

Réduction à partir du problème 3-SAT.

  • Vert ⟶ Vrai = 1
  • Rouge ⟶ Faux = 0
  • Bleu ⟶ ? (degré de liberté)

Gadget :

graph {
    randir=BT;
		x -- n_1;
		y -- n_2;
		n_1 -- z;
		n_2 -- z;
        n_1 -- n_2;

	}

Si $x=y=1$ ⟶ on peut trouver $n_1, n_2$ pour avoir $z=1$

graph {
    randir=BT;
        x[label="1"];
        y[label="1"];
        z[label="1"];
		x -- n_1;
		y -- n_2;
		n_1 -- z;
		n_2 -- z;
        n_1 -- n_2;

	}

Si $x=y=0$ ⟶ on peut trouver $n_1, n_2$ pour avoir $z=0$

graph {
    randir=BT;
        x[label="0"];
        y[label="0"];
        z[label="0"];
		x -- n_1;
		y -- n_2;
		n_1 -- z;
		n_2 -- z;
        n_1 -- n_2;

	}

Si $x=1, y=0$ ⟶ en reliant la sortie à un sommet colorié “?”, on peut forcer $z=1$

graph {
    randir=BT;
        x[label="0"];
        y[label="1"];
        z[label="1"];
        t[label="?"];
		x -- n_1;
		y -- n_2;
		n_1 -- z;
		n_2 -- z;
        z -- t;
        n_1 -- n_2;
	}

⟹ On a presque codé une porte “OU” : avedc ce dispositif (“gadget”), on sait que si $z$ vaut $1$ en sortie, c’est qu’une des entrées valait $1$.

\[f = C_1 ∧ ⋯ ∧ C_n\]

où les $C_i$ sont des 3-clauses.

\[𝛴 = \{x_1, ⋯, x_n\}\]

NP-hard :

On devine un coloriage $h$.

On vérifie que

\[∀(u,v)∈E, h(u) ≠ h(v)\]

NP-completeness:

liaison des sommets $x_1$ $x_2$ ⋯ $x_n$
true $?$ $?$ ⋯ $?$
false $?$ $?$ ⋯ $?$

Dans $C_i$ :

  • Si 1 littéral, on relie $a_i$ à $0$
  • Si 2 littéraux,
graph {
    randir=BT;
        n_1[label="."];
        n_2[label="."];
        z[label="1"];
        t[label="?"];
		a_i1 -- n_1;
		a_i2 -- n_2;
		n_1 -- z;
		n_2 -- z;
        z -- t;
        z -- 0;
        n_1 -- n_2;
	}
  • Si 3 littéraux,
graph {
    randir=BT;
        n_1[label="."];
        n_2[label="."];
        n_3[label="."];
        n_4[label="."];
        z[label="1"];
        zz[label="."];
        t[label="?"];
        tt[label="?"];
		a_i1 -- n_1;
		a_i2 -- n_2;
		n_1 -- z;
		n_2 -- z;
        z -- t;
        z -- n_3;
        n_1 -- n_2;
        n_3 -- n_4;
        a_i3 -- n_4;
        n_4 -- zz;
        n_3 -- zz;  
        zz -- 0;
        zz -- tt;  
	}

EX 5

Réduction du 3-coloring à ce problème.

Soit $h$ un 3-coloriage de $V$.

Soit $G’$ le graphe :

graph {
    randir=BT;
		a -- b;
		b -- c;
		a -- c;
	}

Soit $f(v) =$

  • $a$ si $h(v) = B$
  • $b$ si $h(v) = R$
  • $c$ si $h(v) = G$

Donc $f$ est un homomorphisme.

Réciproquement,

soit $f$ un hom., $h$ le coloriage.

$h(v) =$

  • $B$ si $f(v) = a$
  • $R$ si $f(v) = b$
  • $G$ sinon

Si $(u, v)∈E$, alors $(f(u), f(v))∈E’$.

Donc $f(u)≠f(v)$

Donc $h(u)≠h(v)$

Soit $(u, v)∈E$, on sait $h(v)≠h(u)$.

Donc $f(u)≠f(v)$

Donc $(f(u), f(v))∈E’$

h = ∅

For v∈V :
    Devine v'∈V'
    h = h ∪ {v ⟶ v'}

For (u,v)∈E:
    Si (h(u), h(v))∉E' :
        Echec

Leave a comment