複雑さの階層
計算量理論の分野は、1970年代初頭にStephen CookとLeonid Levinによって独立に提唱され、Richard Karpによって整備されたNP完全性の概念によって飛躍的進歩を遂げた。この概念は、計算量のクラスの性質を、そのクラスの代表的問題を通じて研究することを可能にした。
本書の主眼は、チューリング機械を用いて定義される基本的計算量クラスとその階層構造と包含関係について解説すること、そして、それらのクラスの完全問題を示すことである。紙面の都合上、とりあげることのできなかった発展的内容については、巻末の参考文献などを参照されたい。
なお、本書に登場する用語には、それに対応する英語を示してある。また、外国人名に対しては、少し強引なところもあるが、そのカタカナ読みを付しておいた。読者の参考になればさいわいである。
(「まえがき」より)
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 演習問題およびノート
参考文献
索引