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. 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 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. Per tant, es te que
L ⊆ NL ⊆ P
i per tant, es teL 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
Categoria:Classes de complexitat