NL (計算複雑性理論)
確率的チューリングマシン上で対数領域で解ける問題の複雑性クラスを C とする。C の回答がYESである場合は常に正しいが、回答がNOである場合は3分の1未満の確率で間違った回答だとする。3分の1という定数は、0 ≤ x < 1/2 となる任意の x であればよい。
このようなクラスは NL と同じである。C は時間が多項式時間に制限されていない。なぜなら、対数領域の状態の組み合わせがたかだか多項式で表せるほどしかないとしても、確率的な解法であるために無限ループに陥る可能性があるからである。これを多項式時間に制限すると RLP という別のクラスになる。
C = NL であることを示す。まず C が NL に含まれることを簡単に示すアルゴリズムが存在する。
ある文字列がある言語に含まれない場合、C も NL も全計算経路でこれらを拒否(reject)する。