TD8 : Complexité :

EX 1

1.

Remarquons déjà que : comme il y a $2^n$ valuations possibles, s’il existe une suite d’applications d’opérations qui conduise de $s_{initial}$ à $s_{final}$, alors il en existe une de longueur inférieure à $2^n$ (à chaque opération, on modifie au moins une variable).

Étant donnée une suite d’applications d’opérations, on exécute les opérations de la numéoro $1$ à la numéro $2^n$, puis on renvoie True ssi elle convient.

2.

On réduit les MT calculant en espace $n^k$.

  • Variables :

    • $∀a∈𝛴, ∀p∈⟦1, n^k⟧, a_p$ : “Il y a un $a$ à la $p$-ième case de la bande”.
    • $∀p∈⟦1, \vert Q \vert⟧, q_p$ : “On est dans l’état $q_p$”
    • $∀p∈⟦1, n^k⟧, l_p$ : “La tête de lecture est la position $p$”.

  • $s_{init}$ : $w[0]0, w[1]_1, ⋯, w[\vert w \vert]{\vert w \vert}, l_0, q_{init}$ sont à True

    Le reste est à False.

  • $s_{final}$ : On suppose que la MT a une seule configuration acceptante.

    ex : $$0∧l_0∧q_f$

  • Opérations : Pour tout transition $q, a \mapsto q’, b, →$ et

    $∀p∈⟦1, n^k⟧$,

    • Condition : $l_p∧a_p∧q$

    • Mise à jour :

      • $l_p, a_p, q ← False$
      • $l_{p+1}, b_p, q ← True$

Les opérations sont de taille cste.

  • Taille des opérations : $\vert M \vert × n^k × cste$ : polynomial en $n$

  • Nb de variables : $\vert 𝛴 \vert × n^k + n^k + \vert Q\vert$ : polynomial.

  • $s_{init}, s_{final}$ : taille polynomiale.

PREUVE DE CORRECTION :

Th :

\[∀s, s_{init} ⟶^\ast s ⟺ \widetilde{s_{init}} \vdash_M \widetilde{s}\]

Preuve : Par induction sur $⟶^\ast$.

Lemme :

\[∀s, s_{init} ⟶^\ast s ⟹ ∀p∈⟦1, n^k⟧, ∃!a; s(a_p) = True ∧ ∃!i∈⟦1, n^k⟧; p_i = True ∧ ∃!i∈⟦1, n^k⟧; q_i = True\]

Preuve : Par induction sur la longueur de la réduction de $s_{init}$ vers $s$.

EX 2

3.

Un automate déterministe concurrent a un nombre fini $M = \prod_i^n M_i$ d’états (où $M_i$ est le nombre d’états de $A_i$)

\[L(A_1, A_2, ⋯, A_n) ≠ ∅ ⟺ ∃ w∈L(A_1, ⋯, A_n); \vert w\vert≤M\]

On ne peut pas simplement deviner un mot $w$ et tester s’il est dans $L(A_1, A_2, ⋯, A_n)$, car si $M$ est exponentiel, on n’est pas dans PSPACE.

Taille du compteur :

\[\log(M) ≤ \sum_i M_i\]

Taille mémorisation des états.

$q ⟵ q_{init}^N$

En posant

\[m ≝ 2^{\sum \vert M_i \vert}\] 
For i=1 to m:

    Deviner une lettre a
    Si transition a possible:
        q ⟵ delta(q, a)
    Sinon :
        reject

Si q=q_final:
    Accept
Sinon:
    Reject

4.

  • $\lbrace x_i \rbrace_{i∈⟦1, n⟧}$
  • $\lbrace c_i \rbrace_{i∈⟦1, n⟧}$

$c_k =$

  • $\bigwedge_{i∈I_k}(x_i = 𝛼_{k,i})$
  • $\lbrace (x_i ⟵ 𝛽_{k,i})\rbrace_{i∈I’_k}$
digraph{
V_i -> {F_i, Puits_i}
F_i -> {V_i, Puits_i}
}

  • Si $i∈I_k∩I’_k$ :

    $𝛼_{k,i}⟶𝛽_{k,i}$

    $\overline{𝛼}_{k,i}⟶P_i$

  • Si $i∈I_k\backslash I’_k$ :

    $𝛼_{k,i}⟶P_i$

  • Si $i∈I’_k\backslash I_k$ :

    $V_i⟶𝛽_{k,i}$

    $F_i⟶𝛽_{k,i}$

  • $s_{init}, s_{final}$

  • $q_{i, initial} = s_{init}(i)$
  • $q_{i, final} = s_{final}(i)$

Nb d’arêtes : $2×\sum_k \vert I_k \vert$

Nb de sommets : $3×n$

Par construction, si on a une suite $(c_{k_i}){i∈⟦1,N⟧}$ d’opérations telle que $s{init} ⟶^{(c_{k_i})i} s{final}$.

Si $A$ accepte $k_1, ⋯, k_N$, $q_{initial} ⟶^{k_1, ⋯, k_N} q_{final}$

$∀i<N, q_{initial} ⟶^{k_1, ⋯, k_i} q_i$

Invariant :

$s_{initial} ⟶^{c_{k_1}, ⋯, c_{k_i}} s_i$, avec :

  • $s_{init} = \widetilde{q_{init}}$
  • $s_i = \widetilde{q_i}$
  • $q_N = q_{final}$
  • $s_N = s_{final}$

5.

$G=(V,E)$.

f(V', v, P) =
    Pour v'∈V\V':
        Si (v,v')∈E:
            Si f(V'∪{v'}, v', P') = Faux:
                retourner Vrai
    retourner Faux

Complexité spatiale en pire cas :

Au plus $\vert V \vert$ appels emboîtés.

Chaque appel utilise au plus $\vert V \vert + 2 + \lceil \log \vert V \vert \rceil$

⟶ en $O(\vert V\vert^2)$

Leave a comment