SL (計算複雑性理論)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/10/13 14:34 UTC 版)
計算複雑性理論におけるSLとは、USTCON問題に対数領域還元可能な問題の複雑性クラスである（Symmetric Logspace の略）。USTCON問題とは、無向グラフの2点間に経路があるかどうかを判定する問題であり、言い換えれば2つの頂点が同じ連結部分に属しているかどうかを判定する問題である。多対一還元かチューリング還元かは問われない。SLは本来は「対称性チューリング機械」を使って定義されるが、非常に複雑な定式化であるため、 実際にはUSTCON問題への還元性の方がよく使われる。
| ||||||||||||
- ^ a b Jesper Jansson. Deterministic Space-Bounded Graph Connectivity Algorithms. Manuscript. 1998.
- ^ Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science. pp.161-187. 1982.
- ^ a b c Carme Àlvarez and Raymond Greenlaw. A Compendium of Problems Complete for Symmetric Logarithmic Space. Computational Complexity,pp.9:73–95. 2000.
- ^ Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X.
- ^ a b C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 0-201-53082-1.
- ^ W. J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. System Sci, 4, 2, pp. 177-192. 1970.
- ^ 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.
- ^ 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.
- ^ a b c Noam Nisan and Amnon Ta-Shma. Symmetric logspace is closed under complement. Chicago Journal of Theoretical Computer Science. 1995.
- ^ Omer Reingold. Undirected ST-connectivity in Log-Space. Electronic Colloquium on Computational Complexity. No. 94. (Draft PDF)
[続きの解説]
「SL (計算複雑性理論)」の続きの解説一覧
- 1 SL (計算複雑性理論)とは
- 2 SL (計算複雑性理論)の概要
- 3 L = SL の影響
このページでは「ウィキペディア」からSL (計算複雑性理論)を検索した結果を表示しています。
Weblioに収録されているすべての辞書からSL (計算複雑性理論)を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からSL (計算複雑性理論)を検索
Weblioに収録されているすべての辞書からSL (計算複雑性理論)を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からSL (計算複雑性理論)を検索 - SL (計算複雑性理論)のページへのリンク
