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 :

  • $\forall a\in 𝛴,\forall p\in ⟦1,n^k⟧,a_p$ : “Il y a un $a$ à la $p$-ième case de la bande”.
  • $\forall p\in ⟦1,|Q|⟧,q_p$ : “On est dans l’état $q_p$”
  • $\forall p\in ⟦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^{\prime },b,\to$ et

  $\forall p\in ⟦1,n^k⟧$,

  • Condition : $l_p\wedge a_p\wedge q$

  • Mise à jour :

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

Les opérations sont de taille cste.

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

• Nb de variables : $|𝛴|\times n^k+n^k+|Q|$ : polynomial.

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

PREUVE DE CORRECTION :

Th :

$$\forall s,s_{init}{⟶}^{\ast }s⟺\widetilde{s_{init}}{⊢}_M\tilde{s}$$

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

Lemme :

$$\forall s,s_{init}{⟶}^{\ast }s⟹\forall p\in ⟦1,n^k⟧,\exists !a;s(a_p)=True\wedge \exists !i\in ⟦1,n^k⟧;p_i=True\wedge \exists !i\in ⟦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$)

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

Taille du compteur :

Taille mémorisation des états.

$q⟵q_{init}^N$

En posant

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.

• $\{x_i{\}}_{i\in ⟦1,n⟧}$
• $\{c_i{\}}_{i\in ⟦1,n⟧}$

$c_k=$

• $\underset{i\in I_k}{\bigwedge }(x_i={𝛼}_{k,i})$
• $\{(x_i⟵{𝛽}_{k,i}){\}}_{i\in I_k^{\prime }}$

• Si $i\in I_k\cap I_k^{\prime }$ :

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

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

• Si $i\in I_k\mathrm{\setminus }{I}_k^{\prime }$ :

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

• Si $i\in I_k^{\prime }\mathrm{\setminus }{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\times \sum _k|I_k|$

Nb de sommets : $3\times n$

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

Si $A$ accepte $k_1,\cdots ,k_N$, $q_{initial}{⟶}^{k_1,\cdots ,k_N}{q}_{final}$

$\forall i<N,q_{initial}{⟶}^{k_1,\cdots ,k_i}{q}_i$

Invariant :

$s_{initial}{⟶}^{c_{k_1},\cdots ,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 $|V|$ appels emboîtés.

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

⟶ en $O(|V{|}^2)$