01 / 导读
导读
引用
Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.
章节概要
全书分三部分共二十三章，另有数学背景附录。书目目录的概要称其为研究生入门教材，既介绍计算复杂性理论的新近成果，也介绍经典结果，除数学成熟度外基本不要求其他背景，并有300多道习题及一套精选的提示。
第一部分：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定理入门，以及它对近似困难性意味着什么。
第二部分：Lower Bounds for Concrete Computational Models（第12–16章）
第12–16章：Decision trees；Communication complexity；Circuit lower bounds；Proof complexity；Algebraic computation models
这一部分从抽象的类转向可以真正证明下界的受限模型：决策树、通信协议、电路、证明系统和代数计算模型。
第三部分：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?
第三部分汇集更专门的内容：计数问题、平均情形复杂性、困难性放大与编码、去随机化、扩展图与提取器、用傅里叶分析证明PCP定理，以及证明电路下界的障碍。
附录A：Mathematical background
把数学预备知识集中在一处。
核心概念
第一部分：基本类
- NP完全性：NP中最难问题的概念，是第2章的核心。
- 对角化：分离复杂性类的证明技术。
- 多项式层级与交替：NP之上的复杂性层次。
- 随机计算、交互证明与PCP定理：随机性或交互改变了可验证内容的模型。
第二部分：下界
- 具体模型：决策树、通信协议、电路、证明系统和代数模型等可以证明下界的模型。
第三部分：高级专题
- 去随机化与伪随机性：消除或替代随机性。
- 平均情形复杂性与困难性放大：超越最坏情形的复杂性。
- 电路下界的障碍：为什么现有技术止步不前。
评析
优点
- 专题选择现代。 随机计算、交互证明、密码学、量子计算、PCP定理、去随机化和扩展图与经典内容同处一书，正如书名所承诺的那样。
- 按主题组织。 三个部分分开了基本类、已知下界的具体模型和高级专题，因此一门课可以止于第一部分，也可以再添加第二、三部分中挑选的章节。
- 先修要求低。 目录概要称，除数学成熟度外基本不要求其他背景，并有300多道习题及一套精选提示。
- 教学支持。 作者的网页提供基于本书的课程教学计划和勘误表。
局限
- 初学者负担较重。 第1章直接从计算模型开始，第2章则直接讲NP完全性；对图灵机和归约不熟悉的读者可能需要先读一本更平缓的计算理论教材。
- 第三部分有所取舍。 高级专题比较专门，每个专题一章，因此只能作为入门而非完整论述。
- 宽而不深。 许多专题只用一章呈现，专攻其中某一方向的研究者需要专门资料。
在课程中的定位
Arora与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与Barak从这些书结束之处接续复杂性，先讲计算模型，再经NP、空间、电路和随机性走向研究性专题。
如何使用本书
本书面向希望把复杂性理论作为参考或用于自学的计算机科学、数学和物理学高年级本科生、研究生一年级学生及研究人员。主要先修要求是数学成熟度；学过自动机与可计算性的入门课程会使第一部分更轻松。
实用的阅读方案：
- 核心： 第一部分的第1至8章（模型、NP、对角化、空间、多项式层级、电路、随机性和交互证明）。
- 第一部分选读： 按课程需要选读讲密码学、量子计算和PCP定理的第9至11章。
- 第二部分： 在讲电路的第6章之后阅读；讲电路下界的第14章是它的自然延续。
- 第三部分： 按兴趣选章；第23章解释障碍，很适合作为收尾。
- 附录A：数学背景。
做习题时可在需要时使用提示，教学计划与勘误表请查阅作者的网页。