L (complexitat)
En teoria de la complexitat, la classe de complexitat L, també coneguda com a LSPACE o DLOGSPACE, és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing determinista usant una quantitat logarítmica d'espai.[1][2] Formalment, la màquina de Turing te dues cintes, una per codificar l'entrada i només es pot llegir i l'altra cinta té una mida logarítmica però es pot llegir i escriure.
Relacions amb d'altres classes modifica
L és una subclasse de NL, que és una classe de llenguatges decidibles en un espai logarítmic en una màquina de Turing no determinista. Un problema a NL es pot transformar en un problema d'accessibilitat en un graf dirigit representant estats i transicions de la màquina no determinista i el límit logarítmic a l'espai implica que aquest graf té un nombre polinòmic de vèrtexs i arestes, del que es dedueix que NL està contingut dins la classe de complexitat P.[3] Per tant es te que
L ⊆ NL ⊆ P
i per tant, es te
L també es relaciona amb la classe NC de la següent manera: NC¹ ⊆ L ⊆ NL ⊆ NC². En altres paraules, donat un computador paral·lel C amb un nombre de processadors polinòmic O(nk) per una constant k, qualsevol problema que es pot solucionar a C amb un temps O(log n) és de la classe L i qualsevol problema de L es pot solucionar a C en temps O(log n).
Referències modifica
- ↑ Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264.
- ↑ H., Papadimitriou, Christos. Computational complexity. Reading, Mass.: Addison-Wesley, 1994. ISBN 0201530821.
- ↑ Michael,, Sipser,. Introduction to the theory of computation. Boston: PWS Pub. Co, 1997. ISBN 053494728X.