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

NL es diferente de PSPACE, pero aparte de eso es posible por cada inclusión que las clases sean iguales o no..
Other Languages
Esperanto: NL (komplikeco)
français: NL (complexité)
한국어: NL (복잡도)
português: Complexidade NL
русский: Классы L и NL
српски / srpski: NL (сложеност)
Tiếng Việt: NL (độ phức tạp)