計算理論の基礎  3 (複雑さの理論)

Michael Sipser 著 ; 太田和夫, 田中圭介 監訳 ; 阿部正幸, 植田広樹, 藤岡淳, 渡辺治 訳

[目次]

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

「BOOKデータベース」より

この本の情報

書名 計算理論の基礎
著作者等 Sipser, Michael
太田 和夫
植田 広樹
渡辺 治
田中 圭介
藤岡 淳
阿部 正幸
書名ヨミ ケイサン リロン ノ キソ
書名別名 Introduction to the theory of computation. (2nd ed.)

複雑さの理論
巻冊次 3 (複雑さの理論)
出版元 共立
刊行年月 2008.5
ページ数 p294-507, 48p
大きさ 21cm
ISBN 978-4-320-12209-3
NCID BA86004654
※クリックでCiNii Booksを表示
全国書誌番号
21430920
※クリックで国立国会図書館サーチを表示
言語 日本語
原文言語 英語
出版国 日本
この本を: 
このエントリーをはてなブックマークに追加

このページを印刷

外部サイトで検索

この本と繋がる本を検索

ウィキペディアから連想