|
計算理論の基礎
3 (複雑さの理論)
Michael Sipser 著 ; 太田和夫, 田中圭介 監訳 ; 阿部正幸, 植田広樹, 藤岡淳, 渡辺治 訳
[目次]
- 7 時間の複雑さ(複雑さの測定
- クラスP
- クラスNP
- NP完全性
- 他のNP完全問題)
- 8 領域の複雑さ(Savitchの定理
- クラスPSPACE
- PSPACE完全性
- クラスLとクラスNL
- NLとcoNLの等価性)
- 9 問題の扱いにくさ(階層定理
- 相対化
- 回路の複雑さ)
- 10 計算の複雑さの理論における先進的な話題(近似アルゴリズム
- 確率的アルゴリズム
- 交替性
- 対話証明系
- 並列計算
- 暗号)
「BOOKデータベース」より
|