L (計算複雑性理論)
計算量理論においてLとは、決定性チューリングマシンで対数規模の領域︵メモリ︶を使って解くことができる決定問題の集合である。直観的には対数領域は、入力を参照するポインタを一定数保持するのに使われたり、対数個のブール値フラグを保持するのに使われたりする。
Lと関連する計算量にNLがある。NLは、非決定性チューリングマシン上で対数領域で決定可能な言語のクラスである。従って、
が成り立つ。
また、O(log n) の領域を使用する決定機械は時間2O(log n)=nO(1) 以内で停止するとしてよい。これは、対数領域の機械のとりうる状態の組み合わせの合計である。従って、
が成り立つ。ここで Pは決定性チューリングマシンで多項式時間で解ける問題の集合である。
L完全の意味は還元の定め方が難しい。
あるLに属する問題がL完全であることを﹁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 であるという。
が成り立つ。
また、O(log n) の領域を使用する決定機械は時間2O(log n)=nO(1) 以内で停止するとしてよい。これは、対数領域の機械のとりうる状態の組み合わせの合計である。従って、 が成り立つ。ここで Pは決定性チューリングマシンで多項式時間で解ける問題の集合である。
L完全の意味は還元の定め方が難しい。
あるLに属する問題がL完全であることを﹁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 ed.). Addison Wesley. ISBN 0-201-53082-1 Chapter 16: Logarithmic space, pp.395–408.
- Omer Reingold. Undirected ST-connectivity in Log-Space. 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.
