第０章　準備
　　0.1　アルファベット・語・言語
　　0.2　再帰的定義
　　0.3　２項関係
　　0.4　グラフ
　　0.5　論理式とブール関数
　　0.6　擬似プログラムによるアルゴリズムの記述
　　0.7　漸近記法

第１章　アルゴリズムの数学モデル
　　1.1　歴史的背景
　　1.2　アルゴリズムの本質は？
　　1.3　エルブラン・ゲーデル計算可能関数
　　1.4　帰納的関数
　　1.5　whileプログラム
　　1.6　ラムダ定義可能関数
　　1.7　マルコフアルゴリズム

第２章　チューリング機械
　　2.1　多テープチューリング機械
　　2.2　オフラインTM
　　2.3　両方向テープ
　　2.4　チューリング計算可能関数
　　2.5　問題の符号化（なぜTMがアルゴリズムなのか）
　　2.6　なぜ計算可能関数がアルゴリズムなのか？

第３章　決定性/非決定性TMと計算量
　　3.1　非決定性とは
　　3.2　TMによる計算量

第４章　基本定理
　　4.1　計算量の線形圧縮
　　4.2　テープ本数の削減
　　4.3　１テープTMと交差列
　　4.4　その他の計算量

第５章　計算量のクラスの間の基本的関係
　　5.1　基本的クラス
　　5.2　非決定性vs決定性，時間量vsスペース量
　　5.3　サヴィッチの定理
　　5.4　イマーマン・セレプトセーニィの定理

第６章　計算量の階層
　　6.1　帰納的言語のクラス
　　6.2　決定性計算量の階層
　　6.3　非決定性計算量の階層

第７章　決定不能問題
　　7.1　アルゴリズムが存在しない問題とは
　　7.2　ライスの定理
　　7.3　算術階層
　　7.4　ヒルベルトの第10問題

第８章　問題の還元
　　8.1　還元とは
　　8.2　決定不能問題の還元
　　8.3　完全問題

第９章　NP完全問題
　　9.1　クラスNP
　　9.2　SAT
　　9.3　NP完全問題オンパレード
　　9.4　NP完全問題の間の還元

第10章　なぜNP完全問題なのか？
　　10.1　NP完全問題と暗号系
　　10.2　離散対数問題
　　10.3　オラクル（相対化）
　　10.4　補足：群・環・体とmod nの整数論

第11章　その他の計算量のクラス
　　11.1　クラスcoNP
　　11.2　クラスP
　　11.3　クラスPSPACE
　　11.4　クラスNL
　　11.5　手に負えない問題

第12章　決定問題以外の問題
　　12.1　関数問題
　　12.2　数え上げ問題

参考書案内
索引