NL (計算複雑性理論)
RLは確率的チューリングマシンで対数領域で解ける問題のクラスであり、3分の1未満の確率で間違ってNOと答える可能性のあるクラスである。また、ZPL とも同じであることが知られている。ZPL は乱択アルゴリズムで対数領域で解ける問題のクラスである(誤答はない)。しかし、RLPまたはZPLPとは異なると考えられている。これらは RL や ZPL を多項式時間に制限したもので、書籍によってはこれらを混同している場合もある。
サヴィッチの定理を使って NL を決定性領域に関連付けることもできる。つまり、非決定性アルゴリズムは、決定性機械で高々二乗の領域を使うことでシミュレートできる。サヴィッチの定理によれば、 N L ⊆ S P A C E ( log 2  n ) {\displaystyle \mathbf {NL\subseteq SPACE} (\log ^{2}n)} となる( N L ⊆ L 2 {\displaystyle \mathbf {NL\subseteq L} ^{2}} と同じことである)。この強力な原理は1994年に知られるようになった(Papadimtriou 1994 Problem 16.4.10, "Symmetric space")。