NL (計算複雑性理論)
From Wikipedia, the free encyclopedia
NL（えぬえる、英: Nondeterministic Logarithmic-space）は、計算複雑性理論における決定問題の複雑性クラスの一つである。非決定性チューリングマシンで対数規模の記憶領域を使って解ける問題がこのクラスに属する。
NL は Lを一般化したものである。L は決定性チューリングマシンでの対数領域問題のクラスである。決定性チューリングマシンは非決定性チューリングマシンに含まれるため、L も NL に含まれる。
NLは非決定性領域(NSPACE)の計算資源記法で形式的に定義でき、NL = NSPACE(log n) となる。
計算複雑性理論の研究により、このクラスと他の複雑性クラスの関係が明らかとなり、必要な計算資源も明らかとなってきた。一方、アルゴリズムの研究によって、対数領域で解ける問題も明らかとなってきつつある。しかし、計算複雑性理論の他の分野と同様、NLについての重要な部分は未解決である。
NLの確率的定義（後述）を指して RL と呼ぶこともある。しかし、RLという名称はRLPという複雑性クラスの別名として使われることが多い（RLPとは、確率的チューリングマシンで対数領域と多項式時間で解ける問題のクラス）。
ある複雑性クラスに属する最も難しい問題を指して完全問題という。直観的には、完全問題を効率的に解く方法が判っていれば、それを使ってそのクラスのあらゆる問題を解くことが出来る。すなわち、完全問題はその複雑性クラスの能力の程度を示すものである。
NL完全であることが判っている問題はいくつかある。STCON問題（有向グラフの2点間の経路の有無を問う問題）と2元充足可能性問題はNL完全である。2元充足可能性問題とは、連言標準形の論理式の各節（論理和で表される部分）が2つの変数で構成されているとき、その論理式を真とする変数値の組み合わせが存在するかどうかを問う問題である。以下にそのような論理式の例を示す。なお、~（チルダ）は「否定」を意味する。
- (x1 or ~x3) and (~x2 or x3) and (~x1 or ~x2)
包含関係
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 によれば、次のようになる。
また、NL = RL であることも知られている。RLは確率的チューリングマシンで対数領域で解ける問題のクラスであり、3分の1未満の確率で間違ってNOと答える可能性のあるクラスである。また、ZPL とも同じであることが知られている。ZPL は乱択アルゴリズムで対数領域で解ける問題のクラスである（誤答はない）。しかし、RLPまたはZPLPとは異なると考えられている。これらは RL や ZPL を多項式時間に制限したもので、書籍によってはこれらを混同している場合もある。
サヴィッチの定理を使って NL を決定性領域に関連付けることもできる。つまり、非決定性アルゴリズムは、決定性機械で高々二乗の領域を使うことでシミュレートできる。サヴィッチの定理によれば、 となる（ と同じことである）。この強力な原理は1994年に知られるようになった（Papadimtriou 1994 Problem 16.4.10, "Symmetric space"）。
