NL (clase de complexidá)

De Wikipedia
Saltar a: navegación, buscar
NL (clase de complejidad)

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 ta contenida en NL y ta contenida puramente en PSPACE. Como NL tamién ta 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.


Icono de esbozo
Esti artículu ye un entamu. Puedes ayudar a la Wikipedia n'asturianu ampliándolu