NL (clase de complejidad)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En teoría de la complejidad computacional, la clase de complejidad NL (espacio logarítmico no determinista) es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, por una máquina de Turing no determinista tal que la solución si existe es única. La clase L está contenida en NL y está contenida estrictamente en PSPACE. Como NL también está contenida estrictamente en PSPACE, se concluye que en la relación

L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE
NL es diferente de PSPACE, pero aparte de eso es posible por cada inclusión que las clases sean iguales o no.