複雑さの階層
計算量理論とは、計算にかかる手間（計算の複雑さ）をモデル計算機を用いて系統立てて研究する、理論計算機科学の一分野であり、Juris HartmanisとRichard Stearnsが1965年にアメリカ数学会誌に発表した論文"On the computational complexity of algorithms"によって創設された。その主眼は、計算問題のむずかしさを、それを解くアルゴリズムを実行する手間がどれくらいであるかによってクラス分けし、それらのクラスの性質および相互関係を調べることである。
計算量理論の分野は、1970年代初頭にStephen CookとLeonid Levinによって独立に提唱され、Richard Karpによって整備されたNP完全性の概念によって飛躍的進歩を遂げた。この概念は、計算量のクラスの性質を、そのクラスの代表的問題を通じて研究することを可能にした。
本書の主眼は、チューリング機械を用いて定義される基本的計算量クラスとその階層構造と包含関係について解説すること、そして、それらのクラスの完全問題を示すことである。紙面の都合上、とりあげることのできなかった発展的内容については、巻末の参考文献などを参照されたい。
なお、本書に登場する用語には、それに対応する英語を示してある。また、外国人名に対しては、少し強引なところもあるが、そのカタカナ読みを付しておいた。読者の参考になればさいわいである。
（「まえがき」より）
計算量理論の分野は、1970年代初頭にStephen CookとLeonid Levinによって独立に提唱され、Richard Karpによって整備されたNP完全性の概念によって飛躍的進歩を遂げた。この概念は、計算量のクラスの性質を、そのクラスの代表的問題を通じて研究することを可能にした。
本書の主眼は、チューリング機械を用いて定義される基本的計算量クラスとその階層構造と包含関係について解説すること、そして、それらのクラスの完全問題を示すことである。紙面の都合上、とりあげることのできなかった発展的内容については、巻末の参考文献などを参照されたい。
なお、本書に登場する用語には、それに対応する英語を示してある。また、外国人名に対しては、少し強引なところもあるが、そのカタカナ読みを付しておいた。読者の参考になればさいわいである。
（「まえがき」より）
第1章 準備
1.1 論理
1.2 集合
1.3 グラフ・木
1.4 写像
1.5 言語
1.6 関数の漸近的性状
第2章 チューリング機械の基礎
2.1 チューリング機械による言語の受理
2.2 チューリング機械による計算量クラス
2.3 非決定性チューリング機械による言語の受理
2.4 演習問題およびノート
第3章 基本的包含関係と階層構造
3.1 模倣による包含関係
3.2 時間階層定理と領域階層定理
3.3 非決定性領域クラスの階層構造
3.4 基本的計算量クラス
3.5 演習問題およびノート
第4章 NP完全問題
4.1 還元可能性と完全問題
4.2 SATとNP完全問題
4.3 SATの変形とそのNP完全性
4.4 グラフ理論に関するNP完全問題
4.5 組合せ論に関するNP完全問題
4.6 NP完全とPのあいだの溝
4.7 演習問題およびノート
第5章 NL，PSPACE，EXPTIME，およびNEXPTIMEの完全問題
5.1 NLの完全問題
5.2 P完全問題
5.3 PSPACE完全問題
5.4 EXPTIMEおよびNEXPTIMEの完全問題
5.5 演習問題およびノート
第6章 NPを基にした階層
6.1 多項式時間階層PH
6.2 Σpkの完全問題
6.3 Δp2の完全問題
6.4 クラスDP
6.5 確率的チューリング機械と確率的計算量クラス
6.6 演習問題およびノート
参考文献
索引
1.1 論理
1.2 集合
1.3 グラフ・木
1.4 写像
1.5 言語
1.6 関数の漸近的性状
第2章 チューリング機械の基礎
2.1 チューリング機械による言語の受理
2.2 チューリング機械による計算量クラス
2.3 非決定性チューリング機械による言語の受理
2.4 演習問題およびノート
第3章 基本的包含関係と階層構造
3.1 模倣による包含関係
3.2 時間階層定理と領域階層定理
3.3 非決定性領域クラスの階層構造
3.4 基本的計算量クラス
3.5 演習問題およびノート
第4章 NP完全問題
4.1 還元可能性と完全問題
4.2 SATとNP完全問題
4.3 SATの変形とそのNP完全性
4.4 グラフ理論に関するNP完全問題
4.5 組合せ論に関するNP完全問題
4.6 NP完全とPのあいだの溝
4.7 演習問題およびノート
第5章 NL，PSPACE，EXPTIME，およびNEXPTIMEの完全問題
5.1 NLの完全問題
5.2 P完全問題
5.3 PSPACE完全問題
5.4 EXPTIMEおよびNEXPTIMEの完全問題
5.5 演習問題およびノート
第6章 NPを基にした階層
6.1 多項式時間階層PH
6.2 Σpkの完全問題
6.3 Δp2の完全問題
6.4 クラスDP
6.5 確率的チューリング機械と確率的計算量クラス
6.6 演習問題およびノート
参考文献
索引
