Loading article…
計算複雑性理論において、L （ LSPACE、LOGSPACE、またはDLOGSPACEとも呼ばれる）は、対数量の書き込み可能メモリ空間を使用する決定論的チューリングマシンによって解決できる決定問題を含む複雑性クラスである。[1] [2]正式には、チューリングマシンには2つのテープがあり、1つは入力をエンコードし、読み取りのみ可能であり、[3]もう1つのテープは対数サイズであるが、読み取りと書き込みが可能。対数空間は、入力への定数個のポインター[1]と対数個のブールフラグを保持するのに十分であり、多くの基本的なログスペースアルゴリズムはこのようにメモリを使用する。
完全な問題と論理的特徴づけ
Lのすべての非自明な問題は対数空間還元の下で完全であるため[4]、L完全性の意味のある概念を識別するためにはより弱い還元が必要であり、最も一般的なものは一次還元である。
2004年のオマー・ラインゴールドによる結果では、与えられた無向グラフの2つの頂点間に経路が存在するかどうかという問題であるUSTCONがLに属し、USTCONがSL完全であるためL = SLであることが示された。[5]
この結果の 1 つは、 Lの単純な論理的特徴付けです。つまり、 L には、可換推移閉包演算子 (グラフ理論の用語では、すべての接続されたコンポーネントがクリークに変換されます)を追加した1 階述語論理で表現できる言語が正確に含まれているということです。この結果は、データベースクエリ言語に応用できます。クエリのデータ複雑度は、データ サイズを可変入力として、固定クエリに応答する複雑度として定義されます。この尺度では、リレーショナル代数などで表現される完全な情報 ( nullの概念がない)を持つリレーショナル データベースに対するクエリがLに含まれます。
関連する複雑性クラス
LはNLのサブクラスであり、非決定性チューリングマシン上の対数空間で決定可能な言語のクラスである。NLの問題は、非決定性マシンの状態と状態遷移を表す有向グラフの到達可能性の問題に変換でき、対数空間の境界は、このグラフが多項式数の頂点と辺を持つことを意味し、このことから、NL は決定性多項式時間で解決可能な問題の複雑性クラスPに含まれることになる。 [6]したがって、L ⊆ NL ⊆ Pである。 LがPに含まれることは、より直接的に証明することもできる。O (log n ) 空間を使用する決定器は、可能な構成の総数である 2 O ( log n ) = n O (1)時間 以上を使用することはできない。
さらに、 L はクラスNCと次のように関連しています: NC 1 ⊆ L ⊆ NL ⊆ NC 2。つまり、ある定数kに対して多項式数O ( n k ) のプロセッサを備えた並列コンピュータCが与えられた場合、 CでO (log n ) 時間で解決できる問題はすべてLに存在し、Lの問題はすべてCでO (log 2 n ) 時間で解決できます。
重要な未解決問題としては、L = Pであるかどうか[2]、L = NLであるかどうか[7]などがある。L = NP であるかどうかさえ分かっていない。[8]
関連する関数問題のクラスはFLです。 FL は、対数空間縮小を定義するためによく使用されます。
追加のプロパティ
Lは、ログ スペース Oracle クエリ (大まかに言えば、「ログ スペースを使用する関数呼び出し」) をログ スペースでシミュレートし、各クエリで同じスペースを再利用できるため、それ自体が 低くなります。
その他の用途
logspace の主なアイデアは、logspace に多項式絶対値を格納し、それを使用して入力の位置へのポインターを記憶できることです。
したがって、logspace クラスは、入力が大きすぎてコンピューターのRAMに収まらない計算をモデル化するのに役立ちます。長いDNAシーケンスとデータベースは、特定の時間に入力の一定部分のみが RAM にあり、検査する入力の次の部分を計算するためのポインターがあるため、対数メモリのみを使用する問題の良い例です。
参照
- L/poly、多項式サイズの分岐プログラムの複雑さを捉える L の非一様変種
注記
- ^ ab Sipser (1997)、p. 295、定義8.12
- ^ ab ゲイリー & ジョンソン (1979)、p. 177
- ^ 読み取り/書き込み入力テープでは、シンボルをパッキングすることで線形量のメモリを取得できるため（線形高速化定理の証明のように）、対数空間制約を回避できます。
- ^ Garey & Johnson (1979)、p. 179、定理7.13（主張2）を参照
- ^ Reingold, Omer (2005). 対数空間における無向 ST 連結性。STOC'05 : Proceedings of the 37th Annual ACM Symposium on Theory of Computing 。ACM、ニューヨーク。pp. 376–385。doi :10.1145/1060590.1060647。MR 2181639。ECCC TR04-094 。
- ^ Sipser (1997)、系8.21、p.299。
- ^ シプサー (1997)、p. 297;ゲイリー＆ジョンソン (1979)、p. 180
- ^ 「複雑性理論 - L = NP は可能か」。
参考文献
- Arora, Sanjeev; Barak , Boaz (2009).計算複雑性。現代的なアプローチ。ケンブリッジ大学出版局。ISBN 978-0-521-42426-4.ZBL1193.68112 。
- パパディミトリウ、クリストス (1993)。計算複雑性(第 1 版)。アディソン ウェスレー。第 16 章: 対数空間、pp. 395–408。ISBN 0-201-53082-1。
- シプサー、マイケル (1997)。計算理論入門。PWS 出版。セクション 8.4: クラス L と NL、pp. 294–296。ISBN 0-534-94728-X。
- ガリー、MR ;ジョンソン、DS (1979)。コンピュータと扱いにくさ：NP完全性理論へのガイド。WHフリーマン。セクション7.5：対数空間、 pp.177-181。ISBN 0-7167-1045-5. MR 0519066. OCLC 247570676.
- Cook, Stephen A. ; McKenzie, Pierre (1987). 「決定論的対数空間の完全な問題」(PDF) . Journal of Algorithms . 8 (3): 385–394. doi :10.1016/0196-6774(87)90018-6. ISSN 0196-6774.