NL (計算複雑性理論)
文字列が言語に含まれる場合、NLのアルゴリズムはそれを少なくとも1つの計算経路で受容(accept)し、C のアルゴリズムは少なくとも3分の2の計算経路で受容する。
NL が C に含まれることを示すため、一つの NLアルゴリズムで長さ n の計算経路を無作為に選び、これを 2 回行う。計算経路は長さ n を超えず、全体として 2 個の計算経路があるため、一定確率以上で受容状態となる可能性がある。
問題は、最大値が 2 となるカウンタを保持する領域が対数領域にないことである(O(n)になる)。これに対処するため、カウンタをランダムカウンタとし、単純に n 個のコインを投げて全部のコインが表なら停止または拒否するものとする。この事象の確率は 2 なので、停止するまでの平均ステップ数の期待値は 2 となる。この場合に必要な領域は対数領域に収まる(表になるコインを数えるだけなら O(log n) に収まる)。
以上から、領域だけに着目すれば、確率的なアルゴリズムも非決定性のアルゴリズムも同じ能力を持つことがわかる。
NL は Pに含まれる。これは、2元充足可能性問題に多項式時間のアルゴリズムが存在していることから明らかである。しかし、NL = P かどうか、あるいは L = NL かどうかは未だわかっていない。非決定性領域は補集合演算について閉じているため、NL = co-NL であることが判っている。これは、Neil Immerman と Róbert Szelepcsényi が 1987年にそれぞれ独自に証明した。彼らはこの業績によって1995年のゲーデル賞を受賞している(PSPACEのようなより大きいクラスでは、サヴィッチの定理(1970年)によりPSPACE = NPSPACE、NPSPACE = co-NPSPACEであることが既に知られていた)。
回路計算量理論では、NL はNCの階層に置くことができる。Papadimitriou 1994, Theorem 16.1 によれば、次のようになる。
N C 1 ⊆ L ⊆ N L ⊆ N C 2 {\displaystyle {\mathsf {NC_{1}\subseteq L\subseteq NL\subseteq NC_{2}}}}
また、NL = RL であることも知られている。