複雑さの階層/荻原光徳

荻原光徳
共立出版
アルゴリズム・サイエンスシリーズ 6 数理技法編
ISBN：4320121724/9784320121720
発売日:2006年11月

---

【内容紹介】
計算量理論とは、計算にかかる手間(計算の複雑さ)をモデル計算機を用いて系統立てて研究する、理論計算機科学の一分野であり、Juris HartmanisとRichard Stearnsが1965年にアメリカ数学会誌に発表した論文"On the computational complexity of algorithms"によって創設された。その主眼は、計算問題のむずかしさを、それを解くアルゴリズムを実行する手間がどれくらいであるかによってクラス分けし、それらのクラスの性質および相互関係を調べることである。
計算量理論の分野は、1970年代初頭にStephen CookとLeonid Levinによって独立に提唱され、Richard Karpによって整備されたNP完全性の概念によって飛躍的進歩を遂げた。この概念は、計算量のクラスの性質を、そのクラスの代表的問題を通じて研究することを可能にした。
本書の主眼は、チューリング機械を用いて定義される基本的計算量クラスとその階層構造と包含関係について解説すること、そして、それらのクラスの完全問題を示すことである。紙面の都合上、とりあげることのできなかった発展的内容については、巻末の参考文献などを参照されたい。
なお、本書に登場する用語には、それに対応する英語を示してある。また、外国人名に対しては、少し強引なところもあるが、そのカタカナ読みを付しておいた。読者の参考になればさいわいである。
(「まえがき」より)