L (計算複雑性理論)

L (計算複雑性理論)の最新ニュースをまとめて検索！

計算複雑性理論において、Lとは、決定性チューリングマシンで対数規模のメモリ量を使って解くことができる決定問題の複雑性クラスである。直観的には対数領域は、入力を参照するポインタを一定数保持するのに使われたり、対数個のブール値フラグを保持するのに使われたりする。

Lを一般化したものがNLである。NLは、非決定性チューリングマシン上で対数領域で決定可能な言語のクラスである。従って、 が成り立つ。また、O(log n) の領域を使用する決定機械は 2^{O(log n)}=n^O(1) 以上の時間を使わない。これは、対数領域のとりうる状態の組み合わせの合計である。従って、 が成り立つ。ここで P は決定性チューリングマシンで多項式時間で解ける問題の複雑性クラスである。

Lに属するあらゆる問題は対数領域還元の下で完全である。このことはあまり有効ではなく、より弱い還元を定義することでLにおける完全問題が識別されるが、L完全の一般に受け入れられた定義は存在していない。

未解決の重要な問題として、L = P および L = NL の証明問題がある。

函数問題に関する同様の複雑性クラスを FL という。FL は対数領域還元の定義によく使われる。

2004年10月、Omer Reingold は論文で USTCON 問題が L に属することを示した。USTCON問題とは、無向グラフで2点間の経路があるかどうかを判定する問題である。USTCON問題は、SLという複雑性クラスに属し、SL完全であるとされていたため、L = SL であることが確定した。

この結果、L の性質として一階述語論理に推移閉包演算子を追加したもので表される言語が L に含まれることが判明した。

L は対数領域の神託（おおまかに言えば、対数領域を使う関数呼び出しに相当）を対数領域でシミュレート可能であり、各問合せに同じ領域を使用する。この性質をLがLに対して low であるという。

[編集] 参考文献

• Christos Papadimitriou (1993年). Computational Complexity, 1st edition, Addison Wesley. ISBN 0-201-53082-1.  Chapter 16: Logarithmic space, pp.395–408.
• Undirected ST-connectivity in Log-Space. Omer Reingold. Electronic Colloquium on Computational Complexity. No. 94.
• Michael Sipser (1997年). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Section 8.4: The Classes L and NL, pp.294–296.
• Michael R. Garey and David S. Johnson (1979年). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.  Section 7.5: Logarithmic Space, pp.177–181.