NL (clase de complexidá)

En teoría de la complexidá computacional, la clase de complexidá NL (espaciu logarítmicu non determinista) ye'l conxuntu de los problemes de decisión que puen ser resueltos n'espaciu log(n) (ensin cuntar el tamañu de la entrada), onde n ye'l tamañu de la entrada, por una máquina de Turing non determinista tal que la solución si esiste, ye única. La clase L ta contenida en NL y ta contenida puramente en PSPACE. Como NL tamién ta contenida puramente en PSPACE, conclúyese que na rellación

$L\subseteq NL\subseteq P\subseteq NP\subseteq PSPACE$

NL ye distintu de PSPACE, pero amás d'eso ye dable por cada inclusión que les clases seyan iguales o non.

Referencies

Enllaces esternos

Wikimedia Commons tien conteníu multimedia tocante a NL (clase de complexidá).