L (clase de complexidá)

De Uiquipedia
Saltar a: navegación, buscar
Bot icon2.svg
Artículu de traducción automática a partir de "L (clase de complejidad)" que necesita revisión. Quita l'avisu cuando tea correxíu.

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 también está contenida puramente en PSPACE, conclúyese que na relació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[editar | editar la fonte]