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

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

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

2004年10月、Omer Reigngold は '''SL''' = '''[[L (計算複雑性理論)|L]]''' であることを示した。

== 背景 ==
1982年、Lewis と [[クリストス・パパディミトリウ]] によって'''SL'''が最初に定義された<ref name="Jansson">Jesper Jansson. [http://www.df.lth.se/~jj/Publications/STCON2.ps Deterministic Space-Bounded Graph Connectivity Algorithms]. Manuscript. 1998.</ref><ref name="Lewis_and_Papadimitriou">Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. ''Theoretical Computer Science''. pp.161-187. 1982.</ref>。彼らはUSTCONの属する複雑性クラスを探していて、当時は非決定性が必要とされないにもかかわらず [[NL (計算複雑性理論)|'''NL''']] とされていた。彼らは「対称性チューリング機械」を定義して'''SL'''を定義し、USTCONが'''SL'''-完全であることを示し、次が成り立つことを証明した。
: <math>\mathrm{L} \subseteq \mathrm{SL} \subseteq \mathrm{NL}</math>
ここで、[[L (計算複雑性理論)|'''L''']]は通常の[[チューリングマシン|チューリング機械]]で対数領域で解ける問題のクラスであり、[[NL (計算複雑性理論)|'''NL''']]は[[非決定性チューリング機械]]で対数領域で解ける問題のクラスである。後述するように Reingold は、対数領域に限定したとき、対称性チューリング機械と通常の決定性チューリング機械の能力が同じであるという事実を示した。

== 完全問題 ==
定義から、USTCON は明らかに'''SL'''-完全である（'''SL'''に属する問題は全てUSTCONに還元可能である）。USTCONに直接あるいは間接に還元することで様々な完全問題が見つかり、Àlvarez と Greenlaw がそれらをまとめた<ref name="Compendium">Carme Àlvarez and Raymond Greenlaw. [http://www.cs.armstrong.edu/greenlaw/research/compendium.ps A Compendium of Problems Complete for Symmetric Logarithmic Space]. ''Computational Complexity'',pp.9:73–95. 2000.</ref>。その多くは[[グラフ理論]]における問題である。主なものを以下に列挙する。
* USTCON
* 対称性チューリング機械のシミュレーション: 対称性チューリング機械にある領域を与えたとき、ある入力を受理するか?
* 点素な道（経路）: USTCON を経路長について一般化したもの
* [[2部グラフ]]かどうかの判定、またはグラフを2色で[[グラフ彩色]]できるか?
* 2つの無向グラフが同数の連結部分を持つか?
* グラフの連結部分が偶数個あるか?
* グラフの中のある枝について、それを含む輪があるか?
* 2つのグラフの[[スパニング木]]の枝数が同じか?
* グラフの各枝にそれぞれ異なる重み付けがされているとき、ある枝が最小重みスパニング森に含まれるか?
* [[排他的論理和]] 2-[[充足可能性問題]]: 変項の対 (''x''<sub>''i''</sub>,''x''<sub>''j''</sub>) がいくつかあって、それらについて ''x''<sub>''i''</sub> xor ''x''<sub>''j''</sub> が成り立つ必要があるとき、全体が真となるような変項の値の組み合わせがあるか?

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

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

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

'''SL'''に関する自明でない成果は、1970年に証明された[[サヴィッチの定理]]である。これにより、USTCON を log<sup>2</sup> ''n'' 領域で解くアルゴリズムがもたらされた。しかし、深さ優先探索とは異なり、このアルゴリズムは時間に関しては多項式時間以上の時間がかかることがあり、実用的ではない。この結果から、USTCON および'''SL'''は [[DSPACE]](log<sup>2</sup>''n'') に属することが示された<ref name="Sipser">Michael Sipser. ''Introduction to the Theory of Computation''. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X.</ref><ref name="Papadimitriou">C. Papadimitriou. ''Computational Complexity''. Addison-Wesley, 1994. ISBN 0-201-53082-1.</ref><ref name="Savitch">W. J. Savitch. Relationships between nondeterministic and deterministic tape complexities. ''J. Comput. System Sci'', 4, 2, pp. 177-192. 1970.</ref>。実際にはサヴィッチの定理はもっと広範囲なもので、'''NL'''が DSPACE(log<sup>2</sup>''n'') に属することを示した。

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

1989年、Borodin らはこの結果を出発点として、USTCONの補問題（2つの頂点が別の連結部分に属するか）も'''RLP'''に属することを示した<ref name="Borodin">A. Borodin, [[スティーブン・クック|S. A. Cook]], P. W. Dymond, W. L. Ruzzo, and M. Tompa. [http://portal.acm.org/citation.cfm?id=68485 Two applications of inductive counting for complementation problems]. ''SIAM Journal on Computing'', v.18 n.3, p.559-578. June 1989.</ref>。これにより、USTCONおよび'''SL'''は co-'''RLP''' にも属することになり、'''RLP''' と co-'''RLP''' の交差である '''ZPLP''' に属することが明らかとなった。'''ZPLP''' は、対数領域でかつ多項式時間が期待される[[ラスベガス法]]で解ける問題のクラスである。

1992年、Nisan、Szemerédi、Wigderson は USTCON を log<sup>1.5</sup> ''n'' の領域で解ける決定性の新たなアルゴリズムを発見した<ref name="Jansson" /><ref name="Nisan_and_Ta-Shma">Noam Nisan and Amnon Ta-Shma. [http://citeseer.ist.psu.edu/6378.html Symmetric logspace is closed under complement]. ''Chicago Journal of Theoretical Computer Science''. 1995.</ref>。その後、若干の改良が加えられている。

1995年、Nisan と Ta-Shma は、'''SL''' が補問題について閉じていること（すなわち '''SL''' = co-'''SL'''）を示した。当時、'''SL''' と co-'''SL''' は異なると考えられていた<ref name="Nisan_and_Ta-Shma" /><ref name="Compendium" />。

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

2004年10月、Omer Reigngold は USTCON が実際には [[L (計算複雑性理論)|'''L''']]に属することを示した<ref name="Reingold">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. ([http://www.cs.cas.cz/~savicky/vyuka/vypsl/sl.pdf Draft PDF])</ref>。USTCON は '''SL'''-完全とされていたため、この事実によって '''SL''' = '''L''' であることが判明した。数週間後、Vladimir Trifonov は USTCON を O(log ''n'' log log ''n'') 領域で解く決定性のアルゴリズムを示した。

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

== 脚注 ==
{{Reflist}}

== 参考文献 ==
* Noam Nisan, Endre Szemerédi, and Avi Wigderson. [http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NSW92/stoc.ps Undirected Connectivity in ''O''(log<sup>1.5</sup> ''n'') space]. In ''Proceedings 33rd Annual Symposium on Foundations of Computer Science''. Pittsburgh, PA. IEEE. pp. 24-29. 1992.

{{複雑性クラス}}

[[Category:計算複雑性理論]]
[[Category:数学に関する記事]]