計算複雑性理論において、polyLは、入力サイズに対する多重対数関数で空間計算量が制限されるアルゴリズムによって決定論的チューリングマシン上で解ける決定問題の計算複雑性クラスである。言い換えれば、 polyL = DSPACE ((log n ) O(1) ) であり、ここでnは入力サイズ、O (1)は定数を表す。[1]
L ⊆ P、polyL ⊆ QPと同様です。しかし、polyLとPの関係として証明されているのは、 polyL ≠ Pという関係だけです。 polyL ⊊ Pなのか、P ⊊ polyLなのか、あるいはどちらが他方にも含まれていないのかは不明です。 polyLとNPの関係についても同様です。[2] [3]
polyL ≠ Pの証明の 1 つは、 P は対数空間の多対一縮約の下で完全な問題を抱えているが、空間階層定理によりpolyL はそうではないということである。空間階層定理は、すべての整数 d > 0 に対してDSPACE (log d n ) ⊊ DSPACE (log d + 1 n )が成立することを保証する。 polyL に完全な問題 (これをAと呼ぶ) があったとすると、ある整数 k > 0 に対してDSPACE (log k n )の要素となる。問題BはDSPACE (log k + 1 n )の要素だが、 DSPACE (log k n ) の要素ではないと仮定する。 Aが完全であるという仮定は、 Bについて次の O(log k n ) 空間アルゴリズムを意味する:対数空間でBをAに縮約し、次にO(log k n ) 空間でA を決定する。これはBがDSPACE (log k n )の要素であることを意味し、したがって空間階層定理に違反する。[4]
対数空間多対一縮約におけるpolyLの完全な問題が存在しないことから、Ferrarottiらはこのクラスに対して、パラメータ化された問題から特定のパラメータ値に対して問題を解くpolylog空間マシンへの変換を含む、完全性の異なる概念を定義した。[4]
興味深いサブクラスとしてSC （Steve's Class、 Stephen Cookにちなんで名付けられ、 Nick's Classとの類似性から名付けられた）がある。これは、多項式時間と多重対数空間を同時に用いるチューリングマシンで解ける決定問題のクラスである。これは明らかにP ∩ polyLのサブセットであり、P ∩ polyL よりも厳密に小さい可能性もある。なぜなら、後者の場合、多項式時間と多重対数空間の2つの別々のアルゴリズムがあれば十分であるのに対し、 SCの場合、両方の制約を満たす単一のアルゴリズムが必要であるからである。
決定論的文脈自由言語はSCで認識できる。[5] SCにはランダム化Lと境界誤差確率Lが含まれる。[6]
参考文献
- ^ パパディミトリウ、クリストス・H.（1994）、計算複雑性、アディソン・ウェスレー、p.405、ISBN 978-0-201-53082-7
- ^ 書籍, Ronald V. (1976-02-01). 「並進補題、多項式時間、そして(log n)j空間」.理論計算機科学. 1 (3): 215– 226. doi :10.1016/0304-3975(76)90057-8. ISSN 0304-3975.
- ^ 複雑性動物園：ポリL
- ^ ab フェラロッティ、フラヴィオ;ゴンザレス、セネン。シュヴェ、クラウス・ディーター。 Torres、José Maria Turull (2022)、「Uniform Polylogarithmic space Completeness」、Frontiers in Computer Science、4 845990、doi : 10.3389/FCOMP.2022.845990
- ^ Cook, Stephen A. (1979-04-30). 「決定論的CFLは多項式時間と対数二乗空間で同時に受け入れられる」.第11回ACM計算理論シンポジウム議事録 - STOC '79 . ニューヨーク州ニューヨーク: Association for Computing Machinery. pp. 338– 345. doi :10.1145/800135.804426. ISBN 978-1-4503-7438-5。
- ^ Nisan, Noam (1994-03-01). 「RL ⊆ SC」 .計算複雑性. 4 (1): 1– 11. doi :10.1007/BF01205052. ISSN 1420-8954.
