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 (計算複雑性理論)」の例文・使い方・用例・文例
- SL理論とは、どのようなリーダシップを取るのが望ましいかは、部下が仕事や人間関係をどのように考えているかに応じて適切なものが異なるという考え方だ。
- QSLカードという,アマチュア無線家の交信記念カード
- 次世代の超高速船であるテクノスーパーライナー(TSL)が，2005年春に東京－小笠原航路に導入されることになった。
- 政府と民間が共同でTSLを開発している。
- TSLは空気圧で浮上する双胴船である。
- TSLは，現在の高速船では小さすぎて載せることのできなかった大型トラックも載せることができる。
- １万4500トンのアルミ船体のTSLは，東京と小笠原諸島の父島を約16時間で結ぶと期待される。
- それらの模型には蒸気機関車(SL)や特急｢サンダーバード｣がある。
Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
- SL_(計算複雑性理論)のページへのリンク
