L (計算複雑性理論)のソースを表示

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

'''L'''と関連する計算量に[[NL (計算複雑性理論)|'''NL''']]がある。'''NL'''は、[[非決定性チューリングマシン]]上で[[対数]]領域で決定可能な言語のクラスである。従って、<math>\mathrm{L} \subseteq \mathrm{NL}</math> が成り立つ。

また、O(log ''n'') の領域を使用する決定機械は時間 2<sup>O(log ''n'')</sup>=''n''<sup>O(1)</sup> 以内で停止するとしてよい。これは、対数領域の機械のとりうる状態の組み合わせの合計である。従って、<math>\mathrm{L} \subseteq \mathrm{P}</math> が成り立つ。ここで '''[[P (計算複雑性理論)|P]]''' は決定性チューリングマシンで多項式時間で解ける問題の集合である。

'''L完全'''の意味は還元の定め方が難しい。
ある'''L'''に属する問題が'''L完全'''であることを「'''L'''に属するどんな問題も[[対数領域還元]]可能であること」と定義すると、
'''L'''に属する全ての問題が「'''L完全'''」になってしまうので、あまり意味がない。より弱い還元を使う必要がある。

'''L''' = '''P''' や '''L''' = '''NL''' が正しいかどうかは未解決である。

[[関数問題]]に関する同様の計算量を [[FL (計算複雑性理論)|'''FL''']] という。'''FL''' は[[対数領域還元]]の定義によく使われる。

[[2004年]]10月、Omer Reingold は論文で USTCON 問題が '''L''' に属することを示した。USTCON問題とは、[[グラフ理論|無向グラフ]]で与えられた2点間の経路があるかどうかを判定する問題である。USTCON問題は、'''[[SL (計算複雑性理論)|SL]]'''に属し'''SL完全'''であるため、'''L''' = '''SL''' であることが確定した。

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

'''L''' は対数領域の[[神託機械|神託]]（おおまかに言えば、対数領域を使う関数呼び出しに相当）を対数領域でシミュレート可能であり、各問合せに同じ領域を使用する。この性質を'''L'''が'''L'''に対して low であるという。<!-- low の訳語がわからない（訳者）-->

== 参考文献 ==

* {{cite book|author = Christos Papadimitriou | date = 1993年 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st edition | id = ISBN 0-201-53082-1}} Chapter 16: Logarithmic space, pp.395–408.
* Omer Reingold. [http://www.wisdom.weizmann.ac.il/~reingold/publications/sl.ps Undirected ST-connectivity in Log-Space]. Electronic Colloquium on Computational Complexity. No. 94.
* {{cite book|author = Michael Sipser | date = 1997年 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | id = ISBN 0-534-94728-X}} Section 8.4: The Classes L and NL, pp.294–296.
* {{cite book|author = Michael R. Garey and David S. Johnson | date = 1979年 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | id = ISBN 0-7167-1045-5}} Section 7.5: Logarithmic Space, pp.177–181.

{{複雑性クラス}}

[[カテゴリ:計算複雑性理論]]
[[カテゴリ:数学に関する記事]]
[[カテゴリ:数学のオープンプロブレム]]
[[カテゴリ:複雑性クラス]]
[[カテゴリ:確率的複雑性クラス]]
[[カテゴリ:閉包作用素]]
[[カテゴリ:計算機科学の未解決問題]]