1. 問題点とアルゴリズム 1 |
1.1 問題とは、アルゴリズムとは、そして手に負えない問題とは 1 |
1.2 準備 8 |
2. 計算可能性入門 16 |
2.1 帰納的関数論概観 16 |
2.2 計算の基本要素 20 |
2.3 for-times計算可能性 32 |
2.4 計算不可能性の証明と対角線論法 43 |
2.5 計算不可能性な関数の例 51 |
3. 計算可能性の分析 59 |
3.1 関数から集合へ 59 |
3.2 枚挙可能集合 64 |
3.3 クラスRECとクラスRE 70 |
3.4 還元可能性と完全性 78 |
3.5 RE-完全集合の構造 86 |
4. 計算の複雑さ入門 96 |
4.1 計算の複雑さの理論概観 96 |
4.2 計算時間の計り方 99 |
4.3 階層定理 115 |
5. 代表的な計算量クラス 128 |
5.1 代表的な時間計算量クラス 128 |
5.2 クラスNP 135 |
5.3 計算量クラス間の関係 144 |
6. 多項式時間計算可能性の分析 152 |
6.1 多項式時間還元可能性 152 |
6.2 多項式時間還元可能性にもとづく完全性 163 |
6.3 NP-完全集合の構造 175 |
参考文献 193 |
演習問題の解答 195 |
索引 223 |
ひとこと |
1:計算の複雑さの理論での用語 15 |
2:ソフトウェア・サイエンスのニつの顔 58 |
3:様々な還元可能性 95 |
4:クラスNPの定義 151 |
5:構造的解析はどこへ? 192 |
1. 問題点とアルゴリズム 1 |
1.1 問題とは、アルゴリズムとは、そして手に負えない問題とは 1 |
1.2 準備 8 |