L (complexité) - L (complexity)
Dans la théorie de la complexité computationnelle , L (également connu sous le nom de LSPACE ou DLOGSPACE ) est la classe de complexité contenant les problèmes de décision qui peuvent être résolus par une machine de Turing déterministe en utilisant une quantité logarithmique d' espace mémoire inscriptible . Formellement, la machine de Turing a deux bandes, dont l'une code l'entrée et ne peut être que lue, tandis que l'autre bande a une taille logarithmique mais peut être aussi bien lue qu'écrite. L'espace logarithmique est suffisant pour contenir un nombre constant de pointeurs dans l'entrée et un nombre logarithmique d'indicateurs booléens, et de nombreux algorithmes de base de l'espace log utilisent la mémoire de cette manière.
Problèmes complets et caractérisation logique
Chaque problème non trivial dans L est complet sous des réductions de l'espace logarithmique , des réductions plus faibles sont donc nécessaires pour identifier des notions significatives de L -complétude, les plus courantes étant les réductions du premier ordre .
Un résultat de 2004 d' Omer Reingold montre que USTCON , le problème de savoir s'il existe un chemin entre deux sommets dans un graphe non orienté donné , est dans L , montrant que L = SL , puisque USTCON est SL -complet.
Une conséquence de ceci est une caractérisation logique simple de L : il contient précisément les langages exprimables en logique du premier ordre avec un opérateur de fermeture transitif commutatif ajouté (en termes théoriques de graphes , cela transforme chaque composant connecté en clique ). Ce résultat s'applique aux langages de requête de base de données : la complexité des données d'une requête est définie comme la complexité de répondre à une requête fixe compte tenu de la taille des données comme variable d'entrée. Pour cette mesure, les requêtes sur des bases de données relationnelles avec des informations complètes (n'ayant aucune notion de null ) telles qu'exprimées par exemple en algèbre relationnelle sont en L .
Classes de complexité associées
L est une sous - classe de NL , qui est la classe des langages décidables dans l' espace logarithmique sur une machine de Turing non déterministe . Un problème dans NL peut être transformé en un problème d' accessibilité dans un graphe orienté représentant les états et les transitions d'état de la machine non déterministe, et la borne de l'espace logarithmique implique que ce graphe a un nombre polynomial de sommets et d'arêtes, d'où il suit que NL est contenue dans la classe de complexité P des problèmes résolvables en temps polynomial déterministe. Ainsi L ⊆ NL ⊆ P . L'inclusion de L dans P peut aussi être prouvée plus directement : un décideur utilisant l' espace O (log n ) ne peut pas utiliser plus de 2 O (log n ) = n O (1) temps, car c'est le nombre total de configurations possibles.
L se rapporte en outre à la classe NC de la manière suivante: NC 1 ⊆ L ⊆ NL ⊆ NC 2 . En mots, étant donné un ordinateur parallèle C avec un nombre polynomial O ( n k ) de processeurs pour une constante k , tout problème qui peut être résolu sur C en O (log n ) temps est dans L , et tout problème dans L peut être résolu en temps O (log 2 n ) sur C .
Les problèmes ouverts importants incluent si L = P , et si L = NL . On ne sait même pas si L = NP .
La classe connexe de problèmes de fonction est FL . FL est souvent utilisé pour définir des réductions d'espace de log .
Propriétés supplémentaires
L est faible pour lui-même, car il peut simuler des requêtes oracle dans l'espace de journalisation (en gros, des "appels de fonction qui utilisent l'espace de journalisation") dans l'espace de journalisation, en réutilisant le même espace pour chaque requête.
Autres utilisations
L'idée principale du logspace est que l'on peut stocker un nombre de grandeur polynomiale dans le logspace et l'utiliser pour mémoriser des pointeurs vers une position de l'entrée.
La classe logspace est donc utile pour modéliser le calcul où l'entrée est trop grande pour tenir dans la RAM d'un ordinateur. Les longues séquences d' ADN et les bases de données sont de bons exemples de problèmes où seule une partie constante de l'entrée sera dans la RAM à un moment donné et où nous avons des pointeurs pour calculer la prochaine partie de l'entrée à inspecter, utilisant ainsi uniquement la mémoire logarithmique.
Voir également
- L/poly , une variante non uniforme de L qui capture la complexité des programmes de branchement de taille polynomiale
Remarques
Les références
- Arora, Sanjeev ; Barak, Boaz (2009). Complexité informatique. Une approche moderne . Presse de l'Université de Cambridge . ISBN 978-0-521-42426-4. Zbl 1193.68112 .
- Papadimitriou, Christos (1993). Complexité computationnelle (1ère éd.). Addison Wesley. Chapitre 16 : Espace logarithmique, pp. 395–408. ISBN 0-201-53082-1.
- Sipser, Michael (1997). Introduction à la théorie du calcul . Éditions PWS. Section 8.4 : Les Classes L et NL, pp. 294-296. ISBN 0-534-94728-X.
- Garey, MR ; Johnson, DS (1979). Ordinateurs et intraitabilité : un guide de la théorie de la NP-complétude . WH Freeman. Section 7.5 : Espace logarithmique, pp. 177-181 . ISBN 0-7167-1045-5.
- Cook, Stephen A. ; McKenzie, Pierre (1987). "Problèmes complets pour l'espace logarithmique déterministe" (PDF) . Journal des algorithmes . 8 (3) : 385-394. doi : 10.1016/0196-6774(87)90018-6 . ISSN 0196-6774 .