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 pour lesquels il existe une machine de Turing déterministe qui utilise un espace de taille logarithmique en fonction de la taille de l'entrée. Pour être précis, l'exigence sur l'espace se réfère à l'espace supplémentaire utilisable.

Définition formelle[modifier | modifier le code]

Si l'on appelle \mbox{SPACE}(t(n)), l'ensemble de tous les problèmes qui peuvent être résolus 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)) \ .

Intuition sur les problèmes de L[modifier | modifier le code]

Les problèmes de L sont ceux qui ne permettent que de compter des grandeurs polynomiales en la taille de l'entrée; plus précisément, l'espace disponible permet d'écrire des nombres dont les valeurs sont polynomiales en la taille de l'entrée; ceci permet notamment de mémoriser des positions à l'intérieur de la donnée, et donc en particulier conserver des pointeurs sur la donnée.

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) a été définie à l'origine à travers la notion de machine de Turing symétrique (en). Plus précisément, SL correspond à la classe des problèmes que l'on peut résoudre par une machine de Turing non-déterministe en espace logarithmique telle que :

  • Si la réponse est "oui", il y a un ou plus chemins acceptants.
  • Si la réponse est "non", tous les chemins sont non-acceptants.
  • Enfin, si la machine peut effectuer une transition d'une configuration A vers une configuration B, alors la machine pourra toujours aussi effectuer une transition de la configuration B vers la configuration A (c'est ce que signifie la contrainte de symétrie).

Lewis et Papadimitriou qui introduisirent cette classe montrèrent aussi que le problème USTCON est complet pour cette classe (pour les réductions logarithmiques). Le problème USTCON est défini en deux étapes. D'abord, on considère un problème d'accessibilité dans un graphe, c'est-à-dire l'existence d'un chemin reliant deux sommets. Dans un graphe orienté, le problème de la st-connectivité est le problème de savoir s'il existe un chemin d'un sommet donné s à un sommet donné t. Ce problème est noté STCON. Le même problème, mais dans des graphes non orientés, est noté USTCON (la lettre U est pour undirected). Le résultat de complétude montre que tout problème de SL peut se réduire à USTCON.

La classe SL est entre L et NL, mais un résultat remarquable démontré par Omer Reingold et qui lui a valu le prix Gödel, montre que USTCON peut être résolu en espace logarithmique, et donc que L=SL.

Bibliographie[modifier | modifier le code]

Liens externes[modifier | modifier le code]