NL (clase de complejidad)

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.

• Datos: Q12857599