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：數學背景。
做習題時可在需要時使用提示，教學計畫與勘誤表請查閱作者的網頁。