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.

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

${\displaystyle {\displaystyle L\subseteq NL\subseteq P\subseteq NP\subseteq PSPACE}}$

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(n^k) 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).