計算理論の基礎〈３〉複雑さの理論 （原書第２版）

Ｓｉｐｓｅｒ，Ｍｉｃｈａｅｌ【著】/太田 和夫/田中 圭介【監訳】/阿部 正幸/植田 広樹/藤岡 淳/渡辺 治【訳】

共立出版（2008/05発売）

• サイズ A5判／ページ数 p294／高さ 21cm
• 商品コード 9784320122093
• NDC分類 410.9
• Cコード C3341

出版社内容情報

MIT屈指の名講義，Sipser教授の“Theory of Computation”の講義ノートをもとにまとめられた標準的教科書。

目次

７　時間の複雑さ（複雑さの測定；クラスＰ；クラスＮＰ；ＮＰ完全性；他のＮＰ完全問題）
８　領域の複雑さ（Ｓａｖｉｔｃｈの定理；クラスＰＳＰＡＣＥ；ＰＳＰＡＣＥ完全性；クラスＬとクラスＮＬ；ＮＬとｃｏＮＬの等価性）
９　問題の扱いにくさ（階層定理；相対化；回路の複雑さ）
１０　計算の複雑さの理論における先進的な話題（近似アルゴリズム；確率的アルゴリズム；交替性；対話証明系；並列計算；暗号）

著者等紹介

太田和夫［オオタカズオ］
１９７９年早稲田大学大学院理工学研究科修士課程修了。１９７９‐２００１年ＮＴＴ情報流通プラットフォーム研究所。現在、電気通信大学情報通信工学科教授理学博士。１９９１‐２年マサチューセッツ工科大学客員研究員。１９９５‐８年電気通信大学情報システム学研究科客員教授。１９９９‐２０００年マサチューセッツ工科大学客員教授。専門分野は情報セキュリティ

田中圭介［タナカケイスケ］
１９９７年北陸先端科学技術大学院大学情報科学研究科博士後期課程修了。１９９７‐２００１年ＮＴＴ情報流通プラットフォーム研究所。２００１年東京工業大学大学院情報理工学研究科講師。現在、東京工業大学大学院情報理工学研究科准教授博士（情報科学）。２００６年‐現在、東京大学大学院情報学環・学際情報学府非常勤講師。専門分野は暗号理論、計算の複雑さの理論

阿部正幸［アベマサユキ］
１９９２年東京理科大学大学院電気工学専攻科修士課程修了。現在、ＮＴＴ情報流通プラットフォーム研究所特別研究員、主幹研究員、博士（工学）。１９９６年スイス連邦工科大学客員研究員。専門分野は情報セキュリティ（主に暗号プロトコルの研究開発）

植田広樹［ウエダヒロキ］
１９９４年大阪市立大学大学院理学研究科前期博士課程（修士）修了。１９９４‐２００６年ＮＴＴ情報流通プラットフォーム研究所。現在、ＮＴＴ西日本法人営業本部セキュリティサービス推進室担当課長。専門分野は実験整数論（素因数分解）、コンサルティング（セキュリティ）

藤岡淳［フジオカアツシ］
１９９０年東京工業大学大学院理工学研究科博士課程修了。現在、ＮＴＴ情報流通プラットフォーム研究所主幹研究員。工学博士。１９９３‐４年スイス連邦工科大学客員研究員。１９９７年東海大学非常勤講師。２００１‐３年東京大学客員助教授。２００４‐８年国立情報学研究所客員准教授。専門分野は情報セキュリティ（特に暗号理論）（本データはこの書籍が刊行された当時に掲載されていたものです）
※書籍に掲載されている著者及び編者、訳者、監修者、イラストレーターなどの紹介情報です。

感想・レビュー

※以下の感想・レビューは、株式会社ブックウォーカーの提供する「読書メーター」によるものです。

[tabularavum]

NPの定義が非常にわかりやすく解説してある。メモリにも似たような概念があることは初めて知った

2018/01/01

[いするぎえり]

計算量理論の入門書。証明のアイディアを記し、そのあとに証明がしっかり書かれているのが印象的だった。わかりやすいです。

2014/03/27