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

$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á).