NL (計算複雑性理論)

Nondeterministic Logarithmic-space (NL) の概要

Nondeterministic Logarithmic-space（NL）は、計算複雑性理論における主要な複雑性クラスです。このクラスは、非決定性チューリングマシンを使って、対数規模の記憶領域のみで解決できる決定問題を含みます。NLは、決定性チューリングマシンの対数領域問題を含むクラスであるLの一般化として位置付けられます。この性質から、すべてのLの問題は自動的にNLに属します。実際、NLは非決定性領域（NSPACE）と形式的に定義され、記号としては「NL = NSPACE(log n)」と表現されます。

この分野の研究が進む中、NLクラスに含まれる問題の性質や他の計算複雑性クラスとの関係が徐々に明らかになってきました。特に、アルゴリズムの進展によって、対数領域内で解くことができるさまざまな問題が特定されつつあります。ただし、計算複雑性理論全体と同じく、NLに関連する多くの重要な問いは未解決です。

NL 完全問題

完全問題は、特定の複雑性クラスにおいて最も難易度が高い問題を指します。直感的には、完全問題に効率的に解法が見つかれば、そのクラス内の他のすべての問題も解決可能です。そのため、完全問題は対象となるクラスの能力を象徴しています。

NLクラスにはいくつかの完全問題が存在し、STCON問題（有向グラフの二点間に経路が存在するかの判定）や2元充足可能性問題がその例です。後者は、論理式が真となる変数の組み合わせの存在を問うもので、特に連言標準形の論理式が2つの変数から構成される場合が含まれます。例として、以下の論理式を挙げます。

```
(x1 or ~x3) and (~x2 or x3) and (~x1 or ~x2)
```

包含関係と証明

NLはP（多項式時間クラス）に含まれています。このことは、2元充足可能性問題に多項式時間で解けるアルゴリズムが存在するために明らかです。ただし、NLがPに等しいか、またはLがNLに等しいか（L = NL）は現在も不明です。

また、非決定性領域は補集合に対しても閉じているため、NLはco-NLでもあります。この結果は1987年にNeil ImmermanとRóbert Szelepcsényiによって独自に証明され、その功績により彼らは1995年にゲーデル賞を受賞しました。

回路計算量理論の観点から見ると、NLはNC階層に位置付けられます。これに関する具体的な結果として、次のような含有関係が知られています。

```
NC_1 ⊆ L ⊆ NL ⊆ NC_2
```

また、NL = RLであることも知られており、RLは確率的チューリングマシンで対数領域内の問題を解決するクラスです。確率的な間違いは3分の1未満の確率で発生し、これはZPL（乱択アルゴリズムによる対数領域問題）とも同じです。しかし、これらは異なるクラスであると考えられています。

確率的定義とアルゴリズム

確率的チューリングマシン上で対数領域で扱う問題のクラスをCとした場合、Cの出力が「YES」である場合は常に正しいとされ、「NO」の場合は誤りが3分の1未満の確率で発生します。このクラスCは、NLと同一であり、対数領域の状態の組み合わせが多項式で表せても、確率的な手法ゆえにアルゴリズムが無限ループになる可能性が認められています。多項式時間に制限すると、これがRLPという異なるクラスになります。

CがNLに含まれることを示す手法として、ある文字列が特定の言語に含まれない場合は両方のアルゴリズムがそれを拒否し、言語に含まれる場合はNLが少なくとも1つのパスで受容し、Cはほぼ全てのパスで受容することが挙げられます。

与えられた長さnの計算経路を無作為に選び、これを2n回試行すれば、受容される確率が一定以上に達する可能性が出てきます。ただし、領域に関しては最大でO(n)となるため、これを解決するためにランダムカウンタを用いれば、領域が対数に制約されることが保証されます。

このように、NLとC、さらには確率的なアルゴリズムと非決定的アルゴリズムは、領域に着目すれば同様の能力を持つことが確認されます。

記述計算量

NLは、推移閉包演算子を含む一階述語論理で定義される言語でも表現されます。これにより、NLにおける問題の性質をさらに掘り下げて理解することが可能になります。

この分野のさらなる研究は、未来の計算理論やアルゴリズム開発において重要な意味を持つでしょう。

参考文献

• - Papadimitriou, C. (1994年). “Chapter 16: Logarithmic Space”. Computational Complexity. Addison-Wesley.
• - Michael Sipser (1997年). “Sections 8.4–8.6: The Classes L and NL, NL-completeness, NL equals coNL”. Introduction to the Theory of Computation. PWS Publishing.
• - Introduction to Complexity Theory: Lecture 7. Oded Goldreich.

もう一度検索