L (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant l’informatique théorique
Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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

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]