L (complexité)

En informatique théorique, et notamment dans la théorie de la complexité, la classe L est la classe des problèmes de décision décidés par une machine de Turing déterministe qui utilise un espace de taille logarithmique en fonction de la taille de l'entrée^[1],[2]. Pour être plus précis, l'exigence sur l'espace de taille logarithmique se réfère à l'espace supplémentaire utilisable. Elle est aussi parfois notée LOGSPACE^{[réf. nécessaire]}.

Intuitivement, cette classe contient les problèmes que l'on peut décider avec un nombre constant de pointeurs^[2] sur des cases mémoires de l'entrée du problème et un nombre constant de données supplémentaires (des compteurs dont les valeurs sont entre 0 et une grandeur polynomiale en la taille de l'entrée, des booléens, etc.).

Définition formelle

Si l'on appelle ${\displaystyle {\mbox{SPACE}}(t(n))}$ l'ensemble de tous les problèmes qui sont décidés par des machines de Turing déterministes utilisant un espace ${\displaystyle O(t(n))}$ (en plus de l'entrée) pour une fonction ${\displaystyle t}$ en la taille de l'entrée ${\displaystyle n}$, alors on peut définir L formellement par :

${\displaystyle {\mbox{L}}={\mbox{SPACE}}(\log(n))\ .}$

Exemples de problèmes

Exemples de langages

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].

Multiplication

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)}$.

Relations avec les autres classes de complexité

On connait les inclusions suivantes :

NC¹ ⊆ L ⊆ NL ⊆ AC¹ ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE

On sait aussi que l'inclusion de L dans PSPACE est stricte, donc l'une des inclusions ci-dessus est stricte. Il n'est pas impossible qu'elles le soient toutes^{[réf. nécessaire]}.

Classe SL et problème d'accessibilité dans un graphe non orienté

Lewis et Christos Papadimitriou ont défini en 1982 la variante "symétrique" de L : la classe SL (pour symmetric log-space en anglais). La définition originale^{[réf. nécessaire]} utilise la notion de machine de Turing symétrique au lieu des machines de Turing déterministes classiques. De manière équivalente, SL est la classe des problèmes décidés par une machine de Turing non-déterministe en espace logarithmique, avec la contrainte de symétrie suivante :

• Si la machine peut effectuer une transition d'une configuration A vers une configuration B, alors la machine peut aussi effectuer une transition de la configuration B vers la configuration A.

Ainsi, la classe SL est entre L et NL^{[réf. nécessaire]}. Lewis et Papadimitriou montrèrent que le problème d'accessibilité dans un graphe non orienté est SL-complet (pour les réductions logarithmiques). Ce problème d'accessibilité prend en entrée un graphe non orienté, un sommet s et un sommet t et détermine s'il existe un chemin d'un sommet donné s à un sommet donné t (à noter que la version du problème d’accessibilité pour les graphes orientés est NL-complète).

En 2004, Omer Reingold montre que le problème d'accessibilité dans un graphe non orienté est décidé en espace logarithmique sur une machine déterministe, et donc que L=SL^[6],[7]. La démonstration de Reingold utilise la notion de graphes expanseurs. Ce résultat lui a valu le prix Gödel en 2009.

Notes et références

1. Garey et Johnson 1979, p. 177.
2. Sipser 1997, Definition 8.12, p. 295.
3. Michael Sipser, Introduction to the Theory of Computation, International Thomson Publishing, 1^er décembre 1996, 396 p. (ISBN 0-534-94728-X, lire en ligne), p. 349, Example 8.18
4. (en) Dexter C. Kozen, Theory of Computation, Homework 3. Ex. 1. p. 277
5. Michael Sipser, Introduction to the Theory of Computation, International Thomson Publishing, 1^er décembre 1996, 396 p. (ISBN 0-534-94728-X, lire en ligne), p. 359, Ex. 8.20
6. Omer Reingold, Salil Vadhan et Avi Wigderson, « Entropy waves, the zig-zag graph product, and new constant-degree expanders », Annals of Mathematics, vol. 155, n^o 1,‎ 2002, p. 157–187 (DOI 10.2307/3062153, JSTOR 3062153, MR 1888797, lire en ligne)
7. Omer Reingold, « Undirected connectivity in log-space », Journal of the ACM, vol. 55, n^o 4,‎ 2008, p. 1–24 (lire en ligne)

Bibliographie

• (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 1 (« The computational model —and why it doesn’t matter »)
• Omer Reingold, « Undirected ST-connectivity in Log-Space », Electronic Colloquium on Computational Complexity, n^o 94,‎ 2004 (lire en ligne). Version électronique.
• Omer Reingold, « Undirected connectivity in log-space », Journal of the ACM, vol. 55, n^o 4,‎ 2008, p. 1–24 (DOI 10.1145/1391289.1391291, MR 2445014). Version journal.
• (en) M.R. Garey et D.S. Johnson, Computers and intractability : a guide to the theory of NP-completeness, New York, W.H. Freeman, 1979, 338 p. (ISBN 0-7167-1045-5), Section 7.5: Logarithmic Space, pp. 177–181
• (en) Christos Papadimitriou, Computational Complexity, Reading (Mass), Addison Wesley, 1993, 1st éd., 523 p. (ISBN 0-201-53082-1), Chapter 16: Logarithmic space, pp. 395–408
• (en) Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997, 396 p. (ISBN 0-534-94728-X), Section 8.4: The Classes L and NL, pp. 294–296

Liens externes

• (en) La classe L sur le Complexity Zoo
• (en) La classe SL sur le Complexity Zoo

• Portail de l'informatique théorique