L (計算複雑性理論)

計算量理論におけるLの理解

計算量理論において、Lは決定性チューリングマシンを利用して対数規模の領域（メモリ）で解決可能な決定問題の集合を表します。具体的には、Lに属する問題は、入力データのポインタやラベル付けされたフラグを保持する際に必要な限られたメモリを利用します。

Lとその関連性

Lと関係のある計算量としてNLが存在します。NLは非決定性チューリングマシンによって対数領域内で扱える言語のクラスを指します。こうした背景のもと、以下の関係が成り立ちます。

$$
L \subseteq NL
$$

この関係は、Lに属するすべての問題がNLにも属することを示しています。そのため、NLはより広範囲の問題を扱うことができると考えられます。また、決定性チューリングマシンがO(log n)の領域を使用する場合、時間計算量は以下のように表されます。

$$
2^{O(log n)} = n^{O(1)}
$$

この式は、対数領域の機械が取ることのできる状態の組み合わせの全体を表しており、さらに次の関係も成り立ちます。

$$
L \subseteq P
$$

ここでPは、多項式時間で解決可能な問題の集合です。これにより、Lの範囲はPにも含まれることが明らかです。

L完全の定義と問題

L完全について考えると、それはLに属する任意の問題が対数領域還元可能であることと定義されます。しかし、すべてのLにある問題が同じL完全に分類されてしまうため、あまり意味を成しません。このため、より弱い還元の方法を用いる必要があります。加えて、L = PやL = NLという仮説が正しいのかどうかは未だに解決されていない問いです。

FLとその意義

関数問題における対数領域に関する計算量はFLと呼ばれ、これは対数領域還元の定義において一般的に使われます。

USTCON問題とLの発展

2004年、Omer Reingoldによって発表された研究において、USTCON問題がLに属することが確認されました。USTCON問題は、無向グラフ内の2つのノード間に経路が存在するかを判定する問題となっており、これによりUSTCONはSLにも属し、SL完全であることが判明しました。

この発見は、LとSLが等しいことを確定させるもので、Lの性質において一階述語論理に推移閉包演算子を追加したもので表される言語が含まれることを意味します。加えて、Lは対数領域の神託を対数領域でシミュレート可能であり、各問合せに同じ領域を利用する特性を持っています。この特性をLがLに対して「low」であると呼びます。

参考文献

• - Christos Papadimitriou (1993). Computational Complexity (1st 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.

もう一度検索