計算理論の基礎 [原著第 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 暗号

P と NP 、 NP 完全性、 PSPACE 。計算量クラスの名前は知っていても、その定義と証明を一段ずつ自分の手で追った経験を持つエンジニアは意外に少ないものです。本書は MIT の Michael Sipser 氏による講義をもとにした計算理論の世界的な定番教科書の日本語版で、 3 分冊のうち「複雑さの理論」を扱う第 3 巻にあたります。田中圭介氏、藤岡淳氏らの共訳で共立出版から刊行されています。

内容は時間計算量の測定から始まり、クラス P と NP 、 NP 完全性の証明技法、 Savitch の定理や PSPACE 完全性といった領域計算量、階層定理・相対化・回路計算量へと進み、終章では近似アルゴリズム、確率的アルゴリズム、対話証明系、暗号といった発展的話題まで視野に入れます。定理を述べた後すぐ証明に入らず、まず証明のアイデアを示し、あえて失敗する筋道にも触れて理解を深めさせる叙述が本書の持ち味で、独習でも講義を聴くような呼吸で読み進められます。

前提となるのは第 1 〜 2 巻で扱われるオートマトンと計算可能性の素養、そして大学初年級の離散数学です。「 NP 困難」という言葉を使いながらその根拠を説明できないことにもどかしさを感じている人、暗号理論や大学院の理論系講義に備えたい学生が、腰を据えて取り組むための本格的な教科書です。