L (complexité)

Le langage ${\displaystyle \{0^{k}1^{k}\mid k\in \mathbb {N} \}}$ est dans L[3]. Voici un algorithme qui décide ${\displaystyle \{0^{k}1^{k}\mid k\in \mathbb {N} \}}$ en espace logarithmique :

procedure M(w)
 si w vide
   accepter
 i = 0
 tant que w[i] == 0
     i := i+1
 compteurzero := i
 tant que w[i] == 1
     i := i+1
 si w[i] != ' ' (différent de la fin de mot)
     refuser
 si compteurzero == (i - compteurzero)
     accepter
 sinon
     refuser

Le mot w n'est pas modifié : c'est l'entrée et elle n'est pas comptabilisée dans le calcul de la mémoire utilisée. On ne compte que la mémoire supplémentaire, à savoir, les variables i et compteurzero qui sont des entiers positifs bornées par |w| et que l'on peut coder en espace logarithmique en |w|.

Le langage des mots généré par la grammaire algébrique suivante est dans L : S --> (S) | SS | ε[4].

La représentation binaire de l'entier ${\displaystyle n}$ est notée ${\displaystyle \langle n\rangle }$ dans cette section. Le langage ${\displaystyle \mathrm {MULT} =\left\{(\langle n\rangle ,\langle m\rangle ,\langle n\times m\rangle )\mid n,m\in \mathbb {N} \right\}}$ est dans L[5]. L'algorithme suivant reconnait ${\displaystyle \mathrm {MULT} }$ en utilisant un espace en ${\displaystyle {\mathcal {O}}(\log T)}$, où ${\displaystyle T}$ est la taille de son entrée. L'algorithme prend en entrée trois entiers n, m et p vérifie que la multiplication de n par m vaut bien p. Il calcule à chaque itération le i^e bit du résultat de la multiplication et le compare au i^e bit de p.

Les procédures suivantes sont utilisées dans la description de l'algorithme :

• incrémenter(x), incrémente la variable x ;
• est_un(x, i), indique si le i^e bit de x est non nul, si i est plus grand que la taille de x le bit est considéré comme nul ;
• diviser_par_deux(x), remplace x par le quotient de sa division euclidienne par 2 ; cette opération peut être implémentée comme un décalage des bits de x de un vers les bits de poids faibles.

   procedure verifierMultiplication(n, m, p)
       retenue = 0
       i = 0
       tant que i < max(|n| + |m| - 1, |p|)
           j = 0
           tant que j < i
               k = 0
               tant que k + j <= i
                   si est_un(n, j) et est_un(m, k)
                       incrémenter(retenue)
                   k := k + 1
               si p[i] != retenue[0]
                   rejeter
               diviser_par_deux(retenue)
               j := j + 1
           i := i + 1
       accepter

La valeur des compteurs i, j et k utilisés ne dépasse pas la taille de l'entrée et peuvent donc être codés en espace logarithmique en la taille de l'entrée. Les procédures introduites et les comparaisons utilisent au plus un espace logarithmique en la taille de l'entrée. Enfin, la valeur de la variable retenue ne peut pas dépasser ${\displaystyle \max \left(|n|+|m|-1,|p|\right)^{3}<T^{3}}$, elle peut donc être codée sur un espace en ${\displaystyle {\mathcal {O}}\left(3\log T\right)}$.