計算理論の基礎 [原著第 3 版] 3.複雑さの理論

Michael Sipser 教授による “ Theory of Computation ” の講義は MIT 屈指の名講義で、教室には活気と笑いが絶えることはない。本書はその講義ノートをもとにまとめられた、この分野の標準的教科書である。 定理を述べたあと直ちに証明に取りかからず、証明のアイデアを与える工夫、証明の失敗例に言及して理解を深めさせるなど、随所に講義の雰囲気が感じられる、教育的配慮の行き届いた教科書になっている。 第 3 版では、「決定性文脈自由言語」に関する節が新たに加えられたほか (第 2 巻) 、問題や解答が追加されるとともに、いくつかの話題に関して、第 2 版刊行後の研究の進展について説明を加えた。 第 7 章 時間の複雑さ 7.1 複雑さの測定 7.2 クラス P 7.3 クラス NP 7.4 NP 完全性 7.5 他の NP 完全問題 第 8 章 領域の複雑さ 8.1 Savitch の定理 8.2 クラス PSPACE 8.3 PSPACE 完全性 8.4 クラス L とクラス NL 8.5 NL 完全性 8.6 NL と coNL の等価性 第 9 章 問題の扱いにくさ 9.1 階層定理 9.2 相対化 9.3 回路の複雑さ 第 10 章 計算の複雑さの理論における先進的な話題 10.1 近似アルゴリズム 10.2 確率的アルゴリズム 10.3 交替性 10.4 対話証明系 10.5 並列計算 10.6 暗号