01 / 読書ガイド
読書ガイド
引用
Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.
章の要約
本書は3部23章からなり、数学的背景の付録が付く。書誌カタログの要約は、本書を計算量理論の最近の成果と古典的結果の両方を述べる大学院初学者向けの教科書とし、数学的成熟以外にほぼ予備知識を必要とせず、ヒント付きの選ばれた問題を含む300を超える演習があると述べている。
第I部：Basic Complexity Classes（第1～11章）
第1章：The computational model - and why it doesn't matter
他のすべてが依拠する計算モデルを設定し、主要な結果が特定のモデルの選択に依存しないことを論じる。
第2章：NP and NP completeness
クラスPとNP、およびNP完全性の理論。
第3章：Diagonalization
対角化によって証明される分離結果。
第4章：Space complexity
時間ではなく記憶領域の使用で定義される計算量クラス。
第5章：The polynomial hierarchy and alternations
NPの一般化としての多項式階層と、交代。
第6章：Boolean circuits
チューリング機械に代わるものとしてのブール回路による計算。
第7章：Randomized computation
確率的アルゴリズムと、それをモデル化する計算量クラス。
第8章：Interactive proofs
検証者が証明者と対話する証明系。
第9章：Cryptography
計算量にもとづく暗号の基礎。
第10章：Quantum computation
計算モデルとしての量子計算機と、それに関連する計算量クラス。
第11章：PCP theorem and hardness of approximation: an introduction
PCP定理の入門と、それが近似困難性について何を意味するか。
第II部：Lower Bounds for Concrete Computational Models（第12～16章）
第12～16章：Decision trees；Communication complexity；Circuit lower bounds；Proof complexity；Algebraic computation models
この部は抽象的なクラスから、実際に下界を証明できる制限されたモデルへ向かう。決定木、通信プロトコル、回路、証明系、代数的計算モデルである。
第III部：Advanced Topics（第17～23章）
第17章：Complexity of counting
第18章：Average case complexity: Levin's theory
第19章：Hardness amplification and error correcting codes
第20章：Derandomization
第21章：Pseudorandom constructions: expanders and extractors
第22章：Proofs of PCP theorems and the Fourier transform technique
第23章：Why are circuit lower bounds so difficult?
第III部は、より専門的な内容を集める。数え上げ問題、平均時計算量、困難性増幅と符号、脱乱択、エクスパンダーとエクストラクター、フーリエ解析によるPCP定理の証明、回路下界の証明を阻む障壁である。
付録A：Mathematical background
数学的な前提知識を一か所にまとめたもの。
主要概念
第I部：基本クラス
- NP完全性：NPの中で最も難しい問題という概念で、第2章の中心。
- 対角化：クラスを分離するための証明技法。
- 多項式階層と交代：NPの上にある計算量の階層。
- 乱択計算、対話型証明、PCP定理：乱数や対話が検証可能なことを変えるモデル。
第II部：下界
- 具体的なモデル：決定木、通信プロトコル、回路、証明系、代数的モデルなど、下界を証明できるモデル。
第III部：発展的な話題
- 脱乱択と擬似乱数性：乱数の除去または置き換え。
- 平均時計算量と困難性増幅：最悪の場合を超えた計算量。
- 回路下界の障壁：現在の手法がなぜ届かないのか。
批判的分析
長所
- 現代的な話題の選択。 乱択計算、対話型証明、暗号、量子計算、PCP定理、脱乱択、エクスパンダーが、古典的な内容と同じ本に収められており、題名が約束するとおりである。
- 主題ごとの構成。 3つの部が、基本クラス、下界の知られている具体的なモデル、発展的な話題を分けているので、講義は第I部で終えることも、第II部・第III部から選んだ章を加えることもできる。
- 予備知識の要求が少ない。 カタログの要約は、数学的成熟以外にほぼ予備知識を必要としないと述べ、ヒント付きの選ばれた問題を含む300を超える演習がある。
- 教育面の支援。 著者のページには、本書にもとづく講義の指導計画と正誤表がある。
短所
- 初めて学ぶには負担が大きい。 第1章は計算モデルから、第2章はNP完全性から直接始まる。チューリング機械と帰着に初めて触れる読者は、先にやさしい計算理論の本を読みたいかもしれない。
- 第III部は選択的。 発展的な話題は専門的で、それぞれ1章ずつなので、完全な扱いではなく入門として働く。
- 広く浅い。 多くの話題が1章で示されるので、そのどれかを専門とする研究者は専門的な資料が必要になる。
コースにおける位置づけ
Arora and Barakは、この計算理論のコースにおける高度な計算量の本である。SipserのIntroduction to the Theory of Computationは、オートマトン、計算可能性、計算量への上級向けの入門で、通常の準備になる。Hopcroft、Motwani、UllmanのIntroduction to Automata Theory, Languages, and Computation、LinzとRodgerのAn Introduction to Formal Languages and Automata、KozenのAutomata and Computabilityは、計算量よりもオートマトンと計算可能性をより詳しく扱い、MacCormickの*What Can Be Computed?*はプログラムに理論を結びつける。Arora and Barakは、これらが終わるところから、計算モデルに始まり、NP、空間、回路、乱択を経て研究的な話題へと進んで計算量を取り上げる。
本書の使い方
計算量理論を参考書として、または独学で学びたい、計算機科学、数学、物理学の学部上級生、大学院初年度、研究者に向く。主な前提は数学的成熟で、オートマトンと計算可能性の最初の講義を経ていると第I部が楽になる。
実践的な進め方は次のとおり。
- 中核： 第I部の第1～8章（モデル、NP、対角化、空間、多項式階層、回路、乱択、対話型証明）。
- 第I部からの選択： 講義に応じて、暗号、量子計算、PCP定理の第9～11章。
- 第II部： 回路の第6章の後に読む。回路下界の第14章はその自然な続きになる。
- 第III部： 関心に応じて章を選ぶ。第23章は障壁を説明しており、締めくくりにふさわしい。
- 付録A：数学的背景。
必要に応じてヒントを使いながら演習に取り組み、指導計画と正誤表は著者のページを参照する。