Bibliographic Information

複雑さの理論

Michael Sipser著 ; 阿部正幸 [ほか] 訳

(計算理論の基礎 / Michael Sipser著 ; 阿部正幸 [ほか] 訳, 3)

共立出版, 2008.5

Title Transcription

フクザツサ ノ リロン

Available at  / 229 libraries

Note

原著第2版の翻訳

その他の訳者: 植田広樹, 藤岡淳, 渡辺治

監訳: 太田和夫, 田中圭介

参考文献: 巻末p[1]-6

欧文索引: 巻末p[7]-27

和文索引: 巻末p[29]-48

Description and Table of Contents

Table of Contents

  • 7 時間の複雑さ(複雑さの測定;クラスP;クラスNP;NP完全性;他のNP完全問題)
  • 8 領域の複雑さ(Savitchの定理;クラスPSPACE;PSPACE完全性;クラスLとクラスNL;NLとcoNLの等価性)
  • 9 問題の扱いにくさ(階層定理;相対化;回路の複雑さ)
  • 10 計算の複雑さの理論における先進的な話題(近似アルゴリズム;確率的アルゴリズム;交替性;対話証明系;並列計算;暗号)

by "BOOK database"

Related Books: 1-1 of 1

Details

Page Top