NL (clase de complexidá)

De Uiquipedia
Saltar a: navegación, buscar
Bot icon2.svg
Artículu de traducción automática a partir de "NL (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á NL (espaciu logarítmico non 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 non 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
NL ye distintu de PSPACE, pero amás de eso ye posible por cada inclusión que les clases sían iguales o non.