SL (計算複雑性理論)

提供: miniwiki
移動先:案内、検索

計算複雑性理論におけるSLとは、USTCON問題に対数領域還元可能な問題の複雑性クラスである（Symmetric Logspace の略）。USTCON問題とは、無向グラフの2点間に経路があるかどうかを判定する問題であり、言い換えれば2つの頂点が同じ連結部分に属しているかどうかを判定する問題である。多対一還元かチューリング還元かは問われない。SLは本来は「対称性チューリング機械」を使って定義されるが、非常に複雑な定式化であるため、 実際にはUSTCON問題への還元性の方がよく使われる。

USTCON は STCON（有向到達可能性）問題の特殊ケースである。STCONは有向グラフでの2つの頂点間の経路の有無を判定する問題であり、NL-完全である。USTCON は SL-完全なので、USTCONの解法の進歩は SL にも影響がある。

2004年10月、Omer Reigngold は SL = L であることを示した。

背景

1982年、Lewis と クリストス・パパディミトリウ によってSLが最初に定義された[1][2]。彼らはUSTCONの属する複雑性クラスを探していて、当時は非決定性が必要とされないにも関わらず NL とされていた。彼らは「対称性チューリング機械」を定義してSLを定義し、USTCONがSL-完全であることを示し、次が成り立つことを証明した。

[math]\mathrm{L} \subseteq \mathrm{SL} \subseteq \mathrm{NL}[/math]

ここで、Lは通常のチューリング機械で対数領域で解ける問題のクラスであり、NLは非決定性チューリング機械で対数領域で解ける問題のクラスである。後述するように Reingold は、対数領域に限定したとき、対称性チューリング機械と通常の決定性チューリング機械の能力が同じであるという事実を示した。

完全問題

定義から、USTCON は明らかにSL-完全である（SLに属する問題は全てUSTCONに還元可能である）。USTCONに直接あるいは間接に還元することで様々な完全問題が見つかり、Àlvarez と Greenlaw がそれらをまとめた[3]。その多くはグラフ理論における問題である。主なものを以下に列挙する。

  • USTCON
  • 対称性チューリング機械のシミュレーション: 対称性チューリング機械にある領域を与えたとき、ある入力を受理するか?
  • 点素な道（経路）: USTCON を経路長について一般化したもの
  • 2部グラフかどうかの判定、またはグラフを2色でグラフ彩色できるか?
  • 2つの無向グラフが同数の連結部分を持つか?
  • グラフの連結部分が偶数個あるか?
  • グラフの中のある枝について、それを含む輪があるか?
  • 2つのグラフのスパニング木の枝数が同じか?
  • グラフの各枝にそれぞれ異なる重み付けがされているとき、ある枝が最小重みスパニング森に含まれるか?
  • 排他的論理和 2-充足可能性問題: 変項の対 (xi,xj) がいくつかあって、それらについて xi xor xj が成り立つ必要があるとき、全体が真となるような変項の値の組み合わせがあるか?

これらの補問題もSLに属する。すなわち、SLは補問題について閉じている。

既に L = SL であることは分かっているので、対数領域還元によってさらに多数のSL-完全問題があることがわかっている。LまたはSLに属する問題は全てSL-完全であり、L-完全とSL-完全は等価である。そういった意味で複雑性クラスとしてはあまり重要ではなくなっている。

重要な成果

深さ優先探索や幅優先探索といった古典的アルゴリズムは、USTCONを線形時間と線形領域で解くことができる。これらはSLが定義されるずっと以前からあり、SLがPに属することを証明している。USTCON（すなわちSL）はNLに属することも容易に示すことができる。

SLに関する自明でない成果は、1970年に証明されたサヴィッチの定理である。これにより、USTCON を log2 n 領域で解くアルゴリズムがもたらされた。しかし、深さ優先探索とは異なり、このアルゴリズムは時間に関しては多項式時間以上の時間がかかることがあり、実用的ではない。この結果から、USTCON およびSLは DSPACE(log2n) に属することが示された[4][5][6]。実際にはサヴィッチの定理はもっと広範囲なもので、NLが DSPACE(log2n) に属することを示した。

決定性領域については、サヴィッチの定理以後22年間進歩が見られなかったが、1979年、Aleliunas らはUSTCONの実用的な確率的対数領域アルゴリズムを発見した。これは1つの頂点からランダムウォークし、|V|3 回過ぎても解に到達しないときに受理しないとするアルゴリズムである[5][7]。誤って拒絶する確率は小さく、ランダムウォークを継続するほど指数関数的にその確率が減少していく。これにより、SLはRLPに属することが示された。RLPとは、確率的チューリング機械で多項式時間と対数領域で解くことができ、誤って拒絶する確率は1/3未満とされる複雑性クラスである。

1989年、Borodin らはこの結果を出発点として、USTCONの補問題（2つの頂点が別の連結部分に属するか）もRLPに属することを示した[8]。これにより、USTCONおよびSLは co-RLP にも属することになり、RLP と co-RLP の交差である ZPLP に属することが明らかとなった。ZPLP は、対数領域でかつ多項式時間が期待されるラスベガス法で解ける問題のクラスである。

1992年、Nisan、Szemerédi、Wigderson は USTCON を log1.5 n の領域で解ける決定性の新たなアルゴリズムを発見した[1][9]。その後、若干の改良が加えられている。

1995年、Nisan と Ta-Shma は、SL が補問題について閉じていること（すなわち SL = co-SL）を示した。当時、SL と co-SL は異なると考えられていた[9][3]。

SL = co-SL の重要な系の1つとして、LSL = SL がある。すなわち、決定性の対数領域を持つチューリング機械にSLの神託機械を付加すると、SLに属する問題は明らかに解けるが、それ以外の問題は解けない。これは、ある問題がSLに属することを示すのに、チューリング還元でも多対一還元でもよいということを示している[9][3]。

2004年10月、Omer Reigngold は USTCON が実際には Lに属することを示した[10]。USTCON は SL-完全とされていたため、この事実によって SL = L であることが判明した。数週間後、Vladimir Trifonov は USTCON を O(log n log log n) 領域で解く決定性のアルゴリズムを示した。

L = SL の影響

L = SL であることが判明したことで様々な影響が生じた。明らかに SL-完全問題が全て L に属することになり、全て決定性の対数領域/多項式領域のアルゴリズムで効率的に解ける可能性が示された。特に対数領域還元の利用範囲が広がったと言える。また、USTCON に対数領域還元可能な問題が L に属すると定義されるようになった。

脚注

  1. ↑ 1.0 1.1 Jesper Jansson. Deterministic Space-Bounded Graph Connectivity Algorithms. Manuscript. 1998.
  2. ↑ Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science. pp.161-187. 1982.
  3. ↑ 3.0 3.1 3.2 Carme Àlvarez and Raymond Greenlaw. A Compendium of Problems Complete for Symmetric Logarithmic Space. Computational Complexity,pp.9:73–95. 2000.
  4. ↑ Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X.
  5. ↑ 5.0 5.1 C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 0-201-53082-1.
  6. ↑ W. J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. System Sci, 4, 2, pp. 177-192. 1970.
  7. ↑ Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. 20th Annual Symposium on Foundations of Computer Science, pp.218–223. San Juan, Puerto Rico. IEEE. October 1979.
  8. ↑ A. Borodin, S. A. Cook, P. W. Dymond, W. L. Ruzzo, and M. Tompa. Two applications of inductive counting for complementation problems. SIAM Journal on Computing, v.18 n.3, p.559-578. June 1989.
  9. ↑ 9.0 9.1 9.2 Noam Nisan and Amnon Ta-Shma. Symmetric logspace is closed under complement. Chicago Journal of Theoretical Computer Science. 1995.
  10. ↑ Omer Reingold. Undirected ST-connectivity in Log-Space. Electronic Colloquium on Computational Complexity. No. 94. (Draft PDF)

参考文献

テンプレート:複雑性クラス



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=SL_(計算複雑性理論)&oldid=113001」から取得