En teoría de la complexidá computacional, la clase de complexidá L (LSPACE o espaciu logarítmico determinista) ye'l conxuntu de los problemes de decisión que pueden ser resueltos n'espaciu log(n) (ensin cuntar el tamaño de la entrada), onde n ye'l tamaño de la entrada, por una máquina de Turing determinista tal que la solución si esiste ye única. La clase L está contenida en NL y está contenida puramente en PSPACE. Como NL tamién está contenida puramente en PSPACE, conclúyese que na rellación

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

P ye distintu de NP o bien NP ye distintu de PSPACE, pero nun se sabe cual de los dos inclusiones ye propia.

Ver tamién

• SL (clase de complexidá)

Referencies

Enllaces esternos

• Wikimedia Commons tien conteníu multimedia tocante a L (clase de complexidá).