計算理論の基礎 [原著第 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 といった計算量クラスの名前は知っていても、その定義と証明を自分の手で一段ずつ追った経験を持つエンジニアは多くありません。『計算理論の基礎 [原著第 3 版] 3. 複雑さの理論』 (Michael Sipser 著、田中圭介 / 藤岡淳 監訳、阿部正幸 / 植田広樹 / 太田和夫 / 渡辺治 訳、共立出版、2023 年 5 月刊) は、MIT での Sipser 教授の講義ノートをもとにまとめられた標準的教科書 Introduction to the Theory of Computation, 3rd Edition の日本語版を 3 分冊にしたうちの第 3 巻で、計算の複雑さの理論、すなわち計算量理論を扱います。第 1 巻はオートマトンと言語、第 2 巻は計算可能性の理論で、版元からは 3 巻を合わせた合冊版も刊行されています。

第 7 章から第 10 章、時間の複雑さから対話証明系 / 暗号まで

本巻に収められているのは第 7 章から第 10 章までの 4 章で、章番号は第 1 巻からの通し番号です。第 7 章「時間の複雑さ」は複雑さの測定から始めて、クラス P、クラス NP、NP 完全性、他の NP 完全問題へ進みます。第 8 章「領域の複雑さ」は Savitch の定理、クラス PSPACE と PSPACE 完全性、クラス L とクラス NL、NL 完全性、NL と coNL の等価性を扱い、第 9 章「問題の扱いにくさ」では階層定理、相対化、回路の複雑さを取り上げます。終章となる第 10 章「計算の複雑さの理論における先進的な話題」は近似アルゴリズム、確率的アルゴリズム、交替性、対話証明系、並列計算、暗号の 6 節で、計算量理論が他分野へ広がる出口を一望させる構成です。版元の紹介によれば、定理を述べたあと直ちに証明に取りかからず証明のアイデアを先に与え、証明の失敗例にも言及して理解を深めさせる叙述が本書の特徴で、第 3 版では問題と解答が追加され、第 2 版刊行後の研究の進展についての説明も加わっています。同じく第 3 版で新設された決定性文脈自由言語の節は、版元紹介文では第 2 巻と付記されていますが、著者まえがきで 2.4 節と明記され、版元公開の詳細目次でも第 1 巻の第 2 章に置かれているため、本巻の収録範囲には含まれません。

計算量理論を証明で追う意味、NP 完全性と帰着の技術背景

アルゴリズムの実務で使う 計算量 の見積りは、与えられた手続きの実行時間を入力サイズの関数として評価する作業です。計算量理論はその一段上の問いを扱います。すなわち、ある問題を解くどんな手続きにも共通する限界はどこにあるのか、そして効率的な解法が見つかっていない問題同士はどう結び付いているのかという問いです。NP 完全性の概念は、充足可能性問題をはじめとする多数の問題が多項式時間の帰着で互いに変換でき、どれか一つに多項式時間アルゴリズムがあれば全部にあるという構造を明らかにしました。この帰着の技法を証明の水準で身につけると、目の前の問題が NP 完全問題を含むかどうかを判定し、厳密解を諦めて近似や確率的手法に切り替える判断を根拠付きで下せるようになります。領域計算量やクラス L と NL の議論はメモリ制約下の計算を、対話証明系や暗号の節は、秘密を明かさずに正しさを納得させる対話型の証明や、素因数分解の困難さを安全性の根拠にする暗号方式といった暗号理論の土台を、計算量の言葉で説明します。著者まえがきによれば第 2 巻と第 3 巻では擬似コードを使わず散文体でアルゴリズムを記述する方針が採られており、細部の実装より問題の直観的な理解と概観を重視する姿勢が貫かれています。

学部上級 / 大学院初級の教科書としての前提知識と、分冊の読み方

著者まえがきは本書を計算機科学理論の学部上級あるいは大学院初級の教科書として書いたと述べ、定理を証明することに慣れている学生よりも、そうした経験に乏しい学生を対象にできるよう工夫したとしています。したがって数学的な厳密さは要求されますが、証明の型を一から学ぶ読者を締め出す本ではありません。ただし計算量理論は Turing 機械という計算モデルの上に時間と領域の尺度を載せて組み立てられるため、第 1 巻と第 2 巻で導入されるオートマトン、Turing 機械、判定可能性と帰着の概念を土台として読む形になります。第 3 巻から独立に読み始めるなら、少なくとも Turing 機械の定義と計算可能性の基本は別途押さえておく必要があります。訳者まえがきによれば、初版は合冊でしたが教育現場から高価格で教科書に指定しにくいとの声があり、第 2 版から教科書として指定可能な価格にするための分冊化が行われ、第 3 版では電子版が追加されました。訳者は 1995 年春に NTT 研究所へ招聘教授として招かれた Sipser 教授の講義を受けたメンバーで、計算機科学 の理論科目を教える側と学ぶ側の双方に届く日本語版として、初版から第 3 版まで継続して訳出されています。

競技プログラミングや実装の高速化のために計算量の感覚だけを得たい人には本書は遠回りで、その目的なら アルゴリズム本の選び方 で紹介されている図解や実装中心の本のほうが早く効きます。逆に、情報系の学部で理論科目を履修する学生、大学院の計算量理論や暗号理論の講義に備えたい人、あるいは SAT ソルバーや最適化ライブラリを業務で使いながら NP 困難という言葉の根拠を自分の言葉で説明できるようになりたいエンジニアにとって、定義から証明まで自力で追える本書は、投じた時間が長く効く教科書です。第 1 巻 / 第 2 巻と合わせて腰を据えて取り組む価値のある一冊で、3 分冊のうちどこから手に取るか迷うなら、実務との接点が濃いこの第 3 巻が目標地点になります。