NL（複雑性）

NLとは、非決定性チューリングマシン（NTM）が対数量のメモリ空間を用いて解決できる決定問題の複雑性クラスのことである。

より詳しく言うと、言語${\displaystyle L}$NLであるのは、NTMが存在する場合のみである。${\displaystyle M}$そのため

• ${\displaystyle M}$logspace上で動作します。
• ${\displaystyle M}$必ず停止する。

• もし${\displaystyle x\in L}$そうすれば、少なくとも１つの計算痕跡が存在する${\displaystyle M(x)}$その結果、機械は受理状態のまま停止する。
• もし${\displaystyle x\not \in L}$すると、すべての計算トレースが${\displaystyle M(x)}$その結果、機械は受け入れ不可能な状態で停止する。

C を、確率的チューリングマシンを用いて対数空間で解ける決定問題の複雑性クラスとします。このチューリングマシンは、決して誤って受理することはありませんが、誤って拒否する確率は 1/3 未満です。これを片側エラーと呼びます。定数 1/3 は任意であり、0 ≤ x < 1/2 を満たす任意のxで十分です。

結果として、C = NLであることが判明しました。Cは、決定論的な対応物Lとは異なり、多項式時間に限定されないことに注意してください。これは、C は構成が多項式数であるにもかかわらず、ランダム性を使用して無限ループから抜け出すことができるためです。もし多項式時間に限定すると、クラスRLが得られます。RL は NL に含まれますが、 NLと等しいとは知られておらず、またそう考えられてもいません。

C = NLを証明する簡単なアルゴリズムが存在する。明らかにCはNLに含まれている。なぜなら、次のとおりである。

• 文字列が対象言語に含まれていない場合、両方ともすべての計算パスで拒否します。
• 文字列が対象言語に含まれる場合、NLアルゴリズムは少なくとも1つの計算パスで受理し、Cアルゴリズムは少なくとも計算パスの3分の2で受理する。

NLがCに含まれることを示すには、 NLアルゴリズムを1つ選び、長さnのランダムな計算パスを選択して、これを2n回実行します^。どの計算パスも長さnを超えず、計算パスは全部で^2n個あるため、受理パスに到達する可能性は高いです（定数で下限が定められています）。

^{唯一の問題は、2 n}までカウントできるバイナリカウンタを対数空間に収めるスペースがないことです。この問題を解決するために、 n枚のコインを投げ、すべて表が出たら停止して破棄するランダムカウンタに置き換えます。この事象の確率は 2 ^{− n}なので、停止するまでに平均 2 ⁿステップかかると予想されます。必要なのは、連続して表が出た回数の合計を記録することだけで、これは対数空間でカウントできます。

Immerman–Szelepcsényiの定理によれば、NLは補集合に関して閉じているため、これらの確率的計算における片側誤差はゼロ側誤差に置き換えることができます。つまり、これらの問題は、対数空間を使用し、決してエラーを起こさない確率的チューリングマシンによって解決できます。マシンが多項式時間のみを使用することを要求する対応する複雑性クラスは、ZPLPと呼ばれます。

したがって、空間だけに着目すると、ランダム性と非決定性は同等の力を持っているように思われる。

NLは、 NPなどのクラスと同様に、証明書によって特徴付けることができる。検証器は、追加の読み取り専用で一度だけ読み取れる入力テープを持つ、対数空間で制限された決定性チューリングマシンとする（つまり、検証器は読み取りヘッドを前方にしか移動できず、後方には決して移動できない）。

言語${\displaystyle L}$NLに含まれるのは、 ^{[ 1 ] :定義4.19}の場合に限る。

• 多項式関数が存在する${\displaystyle p}$。
• 検証者が存在する${\displaystyle TM}$。
• いかなる場合でも${\displaystyle x}$、${\displaystyle x\in L}$証明書が存在する場合${\displaystyle u}$長さ${\displaystyle |u|\leq p(|x|)}$、したがって${\displaystyle TM(x,u)=1}$。

言い換えれば、文がその言語に含まれるならば、その文がその言語に含まれることを示す多項式長の証明が存在するということである。文がその言語に含まれない場合については何も述べていないが、イマーマン＝セレプチェニの定理によれば、両方の場合を検証できる検証器が存在することは明らかである。${\displaystyle x\in L}$そして${\displaystyle x\not \in L}$。

読み取り1回条件が必要であることに注意してください。検証者が順方向と逆方向の両方に読み取れる場合、このクラスはNPクラスに拡張されます。^{[ 1 ]：演習4.7}

Cem SayとAbuzer Yakaryılmazは、上記の記述にある決定論的対数空間チューリングマシンは、定数個のランダムビットのみを使用できる有界エラー確率的定数空間チューリングマシンに置き換えることができることを証明した。^{[ 2 ]}

記述的複雑性理論において、自然言語（NL）は、推移閉包演算子を追加した一階述語論理で表現可能な言​​語として定義される。