第１章　はじめに
1.1　アルゴリズムって何
1.2　アルゴリズムの性能
1.3　記法
1.4　グラフとグラフに関する計算問題

第２章　計算モデルと計算可能性
2.1　自然数
2.2　帰納的関数
2.3　ゲーデル数
2.4　λ-定義可能関数
2.5　チューリング機械
2.6　Church-Turingの提唱
2.7　ランダムアクセス機械

第３章　計算可能でない問題
3.1　様々なチューリング機械
3.2　帰納的に可算な問題と計算可能な問題
3.3　計算可能でない問題
3.4　帰着と決定不能問題

第４章　計算量クラスと基本定理
4.1　計算量
4.2　計算量の基本性質
4.3　オーダ記法
4.4　構成可能性と階層定理

第５章　計算量クラスΡとΝΡ
5.1　クラスΡ
5.2　クラスΝΡ
5.3　多項式時間版の帰着と困難性・完全性
5.4　ΝΡ-完全問題
5.5　Cook-Levinの定理の証明
5.6　様々なΝΡ-完全問題

第６章　基本的な計算量クラスとそれらの関係
6.1　基本的な計算量クラス
6.2　補集合の計算量クラスとImmerman-Szelepcenyiの定理
6.3　基本的な計算量クラスに対する完全性
6.4　神託付チューリング機械，チューリング帰着
6.5　多項式時間階層

第７章　おわりに
7.1　確率的な計算の例
7.2　確率計算の計算量クラス
7.3　対話型証明系とグラフ同型判定問題

参考文献
索引