NL (complessità)

Da Wikipedia, l'enciclopedia libera.

La classe NL è una classe di complessità di problemi accettati da una macchina di Turing non deterministica in spazio logaritmico ossia con S_M(n) = O(\log n).

Visto che un problema accettato da una macchina deterministica lo è anche da una non deterministica, avremo che L \subseteq NL.