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　暗号