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

Cette classe est intéressante car elle contient intuitivement 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 \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 O(t(n)) (en plus de l'entrée) pour une fonction t en la taille de l'entrée n, alors on peut définir L formellement par :

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

Exemple[modifier | modifier le code]

Le langage \{0^k1^k \mid k \in  \mathbb N\} est dans L[réf. nécessaire]. Voici un algorithme qui décide \{0^k1^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|.

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.

La classe SL[modifier | modifier le code]

La classe SL (une notation inspirée nom anglais symmetric log-space) est définie à l'origine[réf. nécessaire] à travers la notion de machine de Turing symétrique (en). Plus précisément, SL correspond à la classe des problèmes décidés par une machine de Turing non-déterministe en espace logarithmique, avec une contrainte de symétrie :

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

Lewis et Papadimitriou[réf. nécessaire] qui introduisirent cette classe montrèrent aussi 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).

Un résultat remarquable démontré par Omer Reingold[réf. nécessaire] et qui lui a valu le prix Gödel[réf. nécessaire], 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.

Autre exemples[modifier | modifier le code]

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

  1. Modèle:Harvtxt, p. 177.
  2. a et b Modèle:Harvtxt, Definition 8.12, p. 295.

Bibliographie[modifier | modifier le code]

Liens externes[modifier | modifier le code]