NL (Complexitat)

En teoria de la complexitat, la classe de complexitat NL és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing no determinista usant una quantitat logarítmica d'espai.

NL és una generalització de la classe L. Ja que tota màquina de Turing determinista és també una màquina de Turing no determinsita, L està dins de NL.

NL es pot definir en termes de recursos com NL = NSPACE (log n).

Relacions amb d'altres classes

Es coneix que NL està dins de P, però no se sap si NL = P o bé L = NL. Se sap que NL = co-NL, la classe dels llenguatges que els seus complements son a NL. També es coneix que

${\displaystyle {\mathsf {NC_{1}\subseteq L\subseteq NL\subseteq NC_{2}}}}$

I per tant,

${\displaystyle L\subseteq NL\subseteq P\subseteq NP\subseteq PSPACE}$

Més precisament, NL està dins de la classe AC¹. S'ha demostrat que NL és igual a ZPL, tot i que no se sap si és igual a RPL o ZPLP.

Pel teorema de Savitch s'obté directament que

${\displaystyle {\mathsf {NL\subseteq SPACE}}(\log ^{2}n)\ \ \ \ {\text{equivalentment,}}{\mathsf {NL\subseteq L}}^{2}}$