L (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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ées 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é 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 polynômiale en la taille de l'entrée, des booléens, etc.).

Définition formelle[modifier | modifier le code]

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

Exemple[modifier | modifier le code]

Le langage est dans L[réf. nécessaire]. Voici un algorithme qui décide 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|.

Relations avec les autres classes de complexité[modifier | modifier le code]

On connait les inclusions suivantes :

LNLNCPNPPSPACE

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.

Classe SL et problème d'accessibilité dans un graphe non orienté[modifier | modifier le code]

Lewis et Papadimitriou ont défini en 1982 une autre classe ː 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 (en). 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.

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[3],[4]. Ce résultat lui a valu le prix Gödel en 2009.

Notes et références[modifier | modifier le code]

  1. Garey et Johnson 1979, p. 177.
  2. a et b Sipser 1997, Definition 8.12, p. 295.
  3. Omer Reingold, Salil Vadhan et Avi Wigderson, « Entropy waves, the zig-zag graph product, and new constant-degree expanders », Annals of Mathematics, vol. 155, no 1,‎ , p. 157–187 (DOI 10.2307/3062153, JSTOR 3062153, lire en ligne)
  4. Omer Reingold, « Undirected connectivity in log-space », Journal of the ACM, vol. 55, no 4,‎ , p. 1–24 (lire en ligne)

Bibliographie[modifier | modifier le code]

Liens externes[modifier | modifier le code]