第１章　近似とは
　　1.1　最適化問題
　　1.2　最適化問題vs決定問題

第２章　近似可能性
　　2.1　近似比―近似の精度
　　2.2　定数近似できない問題―最初の例
　　2.3　定数近似できる問題のリスト

第３章　巡回セールスマン問題
　　3.1　TSPの近似―概要
　　3.2　メトリックTSP
　　3.3　(1,2)-TSP
　　3.4　歩き回りTSP

第４章　いくらでも良い近似ができる問題
　　4.1　PTAS
　　4.2　PTASとFPTASの例
　　4.3　強NP完全な決定問題とFPTAS

第５章　近似における完全問題
　　5.1　NP最適化問題における完全性
　　5.2　NPO完全な問題
　　5.3　APX完全な問題
　　5.4　PTAS完全な問題
　　5.5　近似問題のクラスの間の関係

第６章　発見的手法による近似
　　6.1　ヒューリスティックス
　　6.2　確率的な手法

第７章　並列計算
　　7.1　並列計算のモデル1：交代性TM
　　7.2　並列計算量のクラス
　　7.3　線形未満の時間限定ATM
　　7.4　交代回数限定のATM

第８章　逐次計算と並列計算の関係
　　8.1　決定性/非決定性計算量と交代性計算量
　　8.2　もっとATMについて
　　8.3　多項式時間階層

第９章　並列計算のモデル2：論理回路
　　9.1　論理回路―基本的定義
　　9.2　ブール関数の回路計算量

第10章　論理回路と言語
　　10.1　回路計算量の下界
　　10.2　一様論理回路族
　　10.3　アドバイス関数と非一様な論理回路族

第11章　並列計算により高速化できる問題
　　11.1　NC問題
　　11.2　論理回路とATM

第12章　並列計算のモデル3：PRAM
　　12.1　PRAM機械とプログラム
　　12.2　並列アルゴリズムの技法
　　12.3　同時読み込み/書き出しと排他的読み込み/書き出し
　　12.4　PRAMと他のモデルとの関係
　　12.5　並列計算の定律

第13章　乱択/確率性アルゴリズム
　　13.1　乱択アルゴリズムと平均時間計算量
　　13.2　確率性アルゴリズムとは

第14章　確率性TMとその部分クラスたち
　　14.1　基本的定義
　　14.2　多項式時間限定PTMとクラスPP
　　14.3　エラー確率限定PTM：クラスBPP
　　14.4　モンテカルロアルゴリズムとラスベガスアルゴリズム

第15章　戸田の定理
　　15.1　確率性計算と数え上げ問題：導入
　　15.2　パリティ計算量のクラス⊕P
　　15.3　ヴァリアント・ヴァジラーニの定理
　　15.4　PH⊆P^#SAT：ランダム還元から決定性の還元へ
　　15.5　⊕P,#P,PHの相対化

第16章　対話型証明系
　　16.1　決定性対話型証明系
　　16.2　対話型証明系IP
　　16.3　PCP定理

第17章　NP⊆PCP(n³;1)
　　17.1　証明の概要
　　17.2　証明
　　17.3　PCP定理成立に至る小史

第18章　脱ランダム化
　　18.1　脱ランダム化の十分条件：擬似乱数生成器
　　18.2　脱ランダム化の必要条件：回路計算量の下界
　　18.3　擬似乱数生成法

第19章　数理論理学と計算量のクラス
　　19.1　1階述語論理
　　19.2　2階述語論理

第20章　量子計算
　　20.1　量子ビット―量子の世界の基本単位―とその操作
　　20.2　量子コンピュータの数理モデル
　　20.3　量子回路，量子チューリング機械，量子計算量
　　20.4　ショアの因数分解アルゴリズム

第21章　雑多な補足
　　21.1　多項式時間同型性
　　21.2　決定木
　　21.3　平均計算量

参考書案内
索引