NL (clase de complexidá)

De Wikipedia
Saltar a navegación Saltar a la gueta
30-04-2021 11:37

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

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