L (clase de complexidá)

De Wikipedia

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[editar | editar la fonte]


Referencies[editar | editar la fonte]

Enllaces esternos[editar | editar la fonte]