L (clase de complexidá)

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

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