計算複雜性理論在過去三十多年中發展迅速。自1990年以來取得的出人意料的結果和基礎性的結果本身就可以寫出一部書。這些結果涉及的領域非常廣泛，包括：經典複雜性類的機率型新定義（ip=pspace和各種pcp定理）以及它們在近似算法中的應用，肖爾（shor）為量子計算機設計的整數因數分解算法，對人們目前處理著名的p?=np問題 譯文用“p?=np”來表示原文中的“p versus np”。——譯者注的各種方法為什麼未能獲得成功的了解，去随機化理論和基于計算難度的僞随機性，以及随機性提取器和擴張圖等僞随機對象的優美構造。
全書分為三個部分。
第一部分：基本複雜性類。這個部分是對複雜性理論的廣泛介紹。從圖靈機的定義和可計算理論的基本概念開始，這個部分涵蓋了各種基本的時間複雜性類和空間複雜性類，還包含了更現代的一些專題，包括機率算法、互動式證明、密碼學、量子計算機和pcp定理及其應用。
第二部分：具體計算模型的下界。這個部分讨論線上路和判定樹等具體計算模型上用算法求解各種計算任務所需的計算資源的下界。這些計算模型初看起來與圖靈機有很大的差別，但更深入研究将得到它們與圖靈機之間的有趣的互相聯系。
第三部分：進階專題。這個部分主要是1980年以後人們在複雜性理論方面獲得的進展。内容包括計數複雜性、平均複雜性、難度放大、去随機化和僞随機性、pcp定理的證明以及自然證明。
本書的每一章幾乎都可以單獨進行閱讀，但是第1章、第2章和第7章不能跳過。正是這種設計，使得本書可以适用于下面各種不同的讀者。
實體學家、數學家和其他科學家。這個讀者群對計算複雜性理論越來越感興趣，他們特别感興趣的是那些高調的研究結果，例如肖爾算法(shor algorithm)和最近取得的确定型素性測試算法。這個讀者群的知識儲備豐富，他們可以快速通讀第一部分，然後迅速進入第二部分和第三部分，也可以單獨閱讀各個章節并找到了解目前研究結果所需的每個知識點。
本身不從事計算複雜性理論研究的計算機科學家。他們既可以用本書來自學，也可以将本書作為參考書，還可以用本書來講授大學生或研究所學生的計算理論或計算複雜性理論課程。
從事計算複雜性理論研究或者打算從事這種研究的任何人，包括教授和學生。本書講解最新研究結果和進階專題的詳細程度可以讓打算從事複雜性理論和相關領域研究的讀者具有充足的知識儲備。
本書可以作為如下幾類課程的教科書。
大學生的計算理論課程。很多計算機科學系都用西普賽爾(sipser)的書［sip96］來為大學生開設計算複雜性理論這門課。本書可以用作對西普賽爾的教材在一些更現代的專題上的補充，這些專題包括機率算法、密碼學和量子計算。相比于自動機理論和可計算理論的精細劃分，大學生可能會發現這些專題更能令人耳目一新。所需的數學背景是能夠比較自然地閱讀數學證明以及離散數學知識，這些知識通常涵蓋于“離散數學”或“計算機數學”等課程中，而目前多數計算機系都已經開設了這樣的課程。
為高年級大學生和新入學的研究所學生開設的計算複雜性導論課程。本書還可以用來為計算機科學專業的高年級大學生和新入學的研究所學生開設計算複雜性導論課程，以替代1994年帕帕迪米特裡奧(papadimitriou)撰寫的教材［pap94］（該書未包含很多最近的研究成果）。這門課程可以講授第一部分的多數專題，再零星地講授第二部分和第三部分的内容，并且假設學生具備了一定的算法知識和計算理論的知識。
研究所學生的計算複雜性課程。本書也可以作為研究所學生的計算複雜性課程的教材，以培養學生在複雜性理論或者算法和機器學習等相關領域開展研究的能力。這門課程可以用第一部分來複習基本知識，然後進入第二部分和第三部分的進階專題中。本書的内容多于一個學期的教學内容，網站上提供了這門課程的其他幾種教學大綱。
研究所學生讨論班或進階課程。第二部分和第三部分中的各個獨立章節都可以用于複雜性理論的讨論班和進階課程，比如關于去随機化、pcp定理和下界的讨論班或進階課程。
本書網站為這些課程提供了幾種教學計劃和素材。如果你在課程中采用了本書，我們樂意了解情況并得到你的回報。我們要求你不要在網上釋出本書習題的答案，這樣其他人才可以用這些習題給學生留作業或出考題。
在寫作本書的過程中，我們清醒地意識到我們不得不舍棄對一些重要結果的講述。我們希望本書對其他教材的大量引用有助于讀者的進一步閱讀。同時，我們還計劃對本書的網站進行周期性的更新，以幫助讀者了解和浏覽他們感興趣的新結果。
最重要的是，我們希望通過本書将計算複雜性中激動人心的研究結果以及它們對其他學科的深刻影響傳遞給讀者。
讓我們一起為徹底解決p?=np問題而努力吧！
[第0章 記号約定
<a href="https://yq.aliyun.com/articles/108624/">0.2 判定問題/語言</a>
<a href="https://yq.aliyun.com/articles/108633/">0.3 大o記号</a>
<a href="https://yq.aliyun.com/articles/108639/">習題</a>
[第一部分 基本複雜性類
第1章 計算模型——為什麼模型選擇無關緊要
<a href="https://yq.aliyun.com/articles/108648/">1.2 圖靈機</a>
1.2.1 圖靈機的表達能力
<a href="https://yq.aliyun.com/articles/108650/">1.3 效率和運作時間</a>
1.3.1 定義的健壯性
<a href="https://yq.aliyun.com/articles/108652/">1.4 機器的位串表示和通用圖靈機</a>
1.4.1 通用圖靈機
<a href="https://yq.aliyun.com/articles/108657/">1.5 不可計算性簡介</a>
1.5.1 停機問題
1.5.2 哥德爾定理
<a href="https://yq.aliyun.com/articles/108688/">1.6 類p</a>
1.6.1 為什麼模型選擇無關緊要
1.6.2 p的哲學意義
1.6.3 p的争議和解決争議的一些努力
1.6.4 埃德蒙茲的引言
<a href="https://yq.aliyun.com/articles/108702/">1.7 定理1.9的證明：o(tlogt)時間的通用模拟</a>
本章學習内容
本章注記和曆史
<a href="https://yq.aliyun.com/articles/108710/">習題</a>
[第2章 np和np完全性
2.1.1 p和np的關系
2.1.2 非确定型圖靈機
<a href="https://yq.aliyun.com/articles/108732/">2.2 歸約和np完全性</a>
<a href="https://yq.aliyun.com/articles/108758/">2.3 庫克勒維定理：計算的局部性</a>
2.3.1 布爾公式、合取範式和sat問題
2.3.2 庫克勒維定理
2.3.3 準備工作：布爾公式的表達能力
2.3.4 引理2.11的證明
2.3.5 将sat歸約到3sat
2.3.6 深入了解庫克勒維定理
<a href="https://yq.aliyun.com/articles/108768/">2.4 歸約網絡</a>
<a href="https://yq.aliyun.com/articles/108783/">2.6 conp、exp和nexp</a>
2.6.1 conp
2.6.2 exp和nexp
<a href="https://yq.aliyun.com/articles/108804/">2.7 深入了解p、np及其他複雜性類</a>
2.7.1 np的哲學意義
2.7.2 np與數學證明
2.7.3 如果p=np會怎樣
2.7.4 如果np=conp會怎樣
2.7.5 np和np完全之間存在其他複雜性類嗎
2.7.6 np難的處理
2.7.7 更精細的時間複雜性
<a href="https://yq.aliyun.com/articles/108813/">習題</a>
第3章 對角線方法
3.1 時間分層定理
3.2 非确定型時間分層定理
3.3 拉德納爾定理:np非完全問題的存在性
3.4 神喻機器和對角線方法的局限性
3.4.1 邏輯獨立與相對
習題
第4章 空間複雜性
4.1 空間受限計算的定義
4.1.1 格局圖
4.1.2 一些空間複雜性類
4.1.3 空間分層定理
4.2 pspace完全性
4.2.1 塞維奇定理
4.2.2 pspace的本質：最佳博弈政策
4.3 nl完全性
4.3.1 基于證明的nl定義:僅能讀一次的證明
4.3.2 nl=conl
第5章 多項式分層和交錯
5.1 類Σp2
5.2 多項式分層
5.2.1 多項式分層的性質
5.2.2 ph各層的完全問題
5.3 交錯圖靈機
5.3.1 無限次交錯
5.4 時間與交錯：sat的時空平衡
5.5 用神喻圖靈機定義多項式分層
第6章 布爾線路
6.1 布爾線路和p/poly
6.1.1 p/poly和p之間的關系
6.1.2 線路的可滿足性和庫克勒維定理的另一種證明
6.2 一緻線路
6.2.1 對數空間一緻線路族
6.3 納言圖靈機
6.4 p/poly和np
6.5 線路下界
6.6 非一緻分層定理
6.7 線路複雜性類的精細分層
6.7.1 類nc和類ac
6.7.2 p完全性
6.8 指數規模的線路
第7章 随機計算
7.1 機率型圖靈機
7.2 機率型圖靈機示例
7.2.1 尋找中位數
7.2.2 機率型素性測試
7.2.3 多項式恒等測試
7.2.4 二分圖的完美比對測試
7.3 單面錯誤和“零面”錯誤：rp、corp、zpp
7.4 定義的健壯性
7.4.1 準确度常數的作用：錯率歸約
7.4.2 期望運作時間與最壞運作時間
7.4.3 使用比均勻硬币投擲更具一般性的随機選擇
7.5 bpp同其他複雜性類之間的關系
7.5.1 bppp/poly
7.5.2 bppph
7.5.3 分層定理與完全問題
7.6 随機歸約
7.7 空間受限的随機計算
第8章 互動式證明
8.1 互動式證明及其變形
8.1.1 準備工作：驗證者和證明者均為确定型的互動式證明
8.1.2 類ip：機率型驗證者
8.1.3 圖不同構的互動式證明
8.2 公用随機源和類am
8.2.1 私有随機源的模拟
8.2.2 集合下界協定
8.2.3 定理8.12的證明概要
8.2.4 gi能是np完全的嗎
8.3 ip=pspace
8.3.1 算術化
8.3.2 #satd的互動式協定
8.3.3 tqbf的協定：定理8.19的證明
8.4 證明者的能力
8.5 多證明者互動式證明
8.6 程式檢驗
8.6.1 具有驗證程式的語言
8.6.2 随機自歸約與積和式
8.7 積和式的互動式證明
8.7.1 協定
第9章 密碼學
9.1 完全保密及其局限性
9.2 計算安全、單向函數和僞随機數産生器
9.2.1 單向函數：定義和執行個體
9.2.2 用單向函數實作加密
9.2.3 僞随機數産生器
9.3 用單向置換構造僞随機數産生器
9.3.1 不可預測性蘊含僞随機性
9.3.2 引理9.10的證明：戈德賴希勒維定理
9.4 零知識
9.5 應用
9.5.1 僞随機函數及其應用
9.5.2 去随機化
9.5.3 電話投币和比特承諾
9.5.4 安全的多方計算
9.5.5 機器學習的下界
第10章 量子計算
10.1 量子怪相：雙縫實驗
10.2 量子疊加和量子位
10.2.1 epr悖論
10.3 量子計算的定義和bqp
10.3.1 線性代數預備知識
10.3.2 量子寄存器及其狀态向量
10.3.3 量子操作
10.3.4 量子操作執行個體
10.3.5 量子計算與bqp
10.3.6 量子線路
10.3.7 傳統計算是量子計算的特例
10.3.8 通用操作
10.4 格羅弗搜尋算法
10.5 西蒙算法
10.5.1 定理10.14的證明
10.6 肖爾算法:用量子計算機實作整數分解
10.6.1 zm上的傅裡葉變換
10.6.2 zm上的量子傅裡葉變換
10.6.3 肖爾的階發現算法
10.6.4 因數分解歸約為階發現
10.6.5 實數的有理數近似
10.7 bqp和經典複雜性類
10.7.1 量子
第11章 pcp定理和近似難度簡介
11.1 動機：近似求解np難的優化問題
11.2 用兩種觀點了解pcp定理
11.2.1 pcp定理與局部可驗證明
11.2.2 pcp定理與近似難度
11.3 兩種觀點的等價性
11.3.1 定理11.5與定理11.9的等價性
11.3.2 重新審視pcp的兩種了解
11.4 頂點覆寫問題和獨立集問題的近似難度
11.5 nppcp(poly(n),1):由沃爾什哈達瑪編碼得到的pcp
11.5.1 線性測試與沃爾什哈達瑪編碼
11.5.2 定理11.19的證明
第二部分 具體計算模型的下界
第12章 判定樹
12.1 判定樹和判定樹複雜性
12.2 證明複雜性
12.3 随機判定樹
12.4 證明判定樹下界的一些技術
12.4.1 随機複雜性的下界
12.4.2 敏感性
12.4.3 次數方法
第13章 通信複雜性
13.1 雙方通信複雜性的定義
13.2 下界方法
13.2.1 詐集方法
13.2.2 鋪砌方法
13.2.3 秩方法
13.2.4 差異方法
13.2.5 證明差異上界的一種技術
13.2.6 各種下界方法的比較
13.3 多方通信複雜性
13.4 其他通信複雜性模型概述
第14章 線路下界：複雜性理論的滑鐵盧
14.1 ac0和哈斯塔德開關引理
14.1.1 哈斯塔德開關引理
14.1.2 開關引理的證明
14.2 帶“計數器”的線路:acc
14.3 單調線路的下界
14.3.1 定理14.7的證明
14.4 線路複雜性的前沿
14.4.1 用對角線方法證明線路下界
14.4.2 acc vs p的研究現狀
14.4.3 具有對數深度的線性線路
14.4.4 線路圖
14.5 通信複雜性方法
14.5.1 與acc0線路之間的聯系
14.5.2 與線性規模對數深度的線路之間的聯系
14.5.3 與線路圖之間的聯系
14.5.4 卡奇梅爾維格德爾森通信遊戲
與深度下界
第15章 證明複雜性
15.1 幾個例子
15.2 命題演算與歸結
15.2.1 用瓶頸法證明下界
15.2.2 插值定理和歸結的指數下界
15.3 其他證明系統概述
15.4 元數學的思考
第16章 代數計算模型
16.1 代數直線程式和代數線路
16.1.1 代數直線程式
16.1.2 例子
16.1.3 代數線路
16.1.4 代數線路中類似于p、np的複雜性類
16.2 代數計算樹
16.2.1 下界的拓撲方法
16.3 布盧姆舒布斯梅爾模型
16.3.1 複數上的複雜性類
16.3.2 完全問題和希爾伯特零點定理
16.3.3 判定性問題——曼德勃羅集
第三部分 進階專題
第17章 計數複雜性
17.1 計數問題舉例
17.1.1 計數問題與機率估計
17.1.2 計數可能難于判定
17.2 複雜性類#p
17.2.1 複雜性類pp：類似于#p的判定問題
17.3 #p完全性
17.3.1 積和式和瓦利安特定理
17.3.2 #p問題的近似解
17.4 戶田定理：php#sat
17.4.1 過渡：具有唯一解的布爾滿足性問題
17.4.2 ⊕的性質和對np、conp證明引理17.17
17.4.3 引理17.17的證明：一般情形
17.4.4 第二步：轉換為确定型歸約
17.5 待決問題
第18章 平均複雜性:勒維定理
18.1 分布問題與distp
18.2 “實際分布”的形式化定義
18.3 distnp及其完全問題
18.3.1 distnp的一個完全問題
18.3.2 p可抽樣的分布
18.4 哲學意義和實踐意義
第19章 難度放大和糾錯碼
19.1 從溫和難度到強難度：姚期智xor引理
19.1.1 用因帕利亞佐難度核引理證明姚期智xor引理
19.1.2 因帕利亞佐難度核引理的證明
19.2 工具：糾錯碼
19.2.1 顯式糾錯碼
19.2.2 沃爾什哈達瑪糾錯碼
19.2.3 裡德所羅門糾錯碼
19.2.4 裡德穆勒糾錯碼
19.2.5 拼接糾錯碼
19.3 高效解碼
19.3.1 裡德所羅門解碼
19.3.2 拼接解碼
19.4 局部解碼與難度放大
19.4.1 沃爾什哈達瑪糾錯碼的局部解碼算法
19.4.2 裡德穆勒糾錯碼的局部解碼算法
19.4.3 拼接糾錯碼的局部解碼算法
19.4.4 局部解碼算法綜合運用于難度放大
19.5 清單解碼
19.5.1 裡德所羅門糾錯碼的清單解碼
19.6 局部清單解碼：接近bpp=p
19.6.1 沃爾什哈達瑪糾錯碼的局部清單解碼
19.6.2 裡德穆勒糾錯碼的局部清單解碼
19.6.3 拼接糾錯碼的局部清單解碼
19.6.4 局部清單解碼算法綜合運用于難度放大
第20章 去随機化
20.1 僞随機數産生器和去随機化
20.1.1 用僞随機數産生器實作去随機化
20.1.2 難度與去随機化
20.2 定理20.6的證明：尼散維格德爾森構造
20.2.1 兩個示意性例子
20.2.2 尼散維格德爾森構造
20.3 一緻假設下的去随機化
20.4 去随機化需要線路下界
第21章 僞随機構造:擴張圖和提取器
21.1 随機遊走和特征值
21.1.1 分布向量和參數λ(g)
21.1.2 無向連通性問題的随機算法的分析
21.2 擴張圖
21.2.1 代數定義
21.2.2 組合擴張和擴張圖的存在性
21.2.3 代數擴張圖蘊含組合擴張圖
21.2.4 組合擴張圖蘊含代數擴張圖
21.2.5 用擴張圖設計糾錯碼
21.3 擴張圖的顯式構造
21.3.1 旋轉映射
21.3.2 矩陣乘積和路徑乘積
21.3.3 張量積
21.3.4 替換乘積
21.3.5 顯式構造
21.4 無向連通性問題的确定型對數空間算法
21.4.1 連通性問題的對數空間算法（定理21.21的證明）
21.5 弱随機源和提取器
21.5.1 最小熵
21.5.2 統計距離
21.5.3 随機性提取器的定義
21.5.4 提取器的存在性證明
21.5.5 基于哈希函數構造提取
21.5.6 基于擴張圖的随機遊走構造提取器
21.5.7 由僞随機數産生器構造提取器
21.6 空間受限計算的僞随機數産生器
第22章 pcp定理的證明和傅裡葉變換技術
22.1 非二進制字母表上的限制滿足問題
22.2 pcp定理的證明
22.2.1 pcp定理的證明思路
22.2.2 迪納爾鴻溝放大：引理22.5的證明
22.2.3 擴張圖、随機遊走和indset的近似難度
22.2.4 迪納爾鴻溝放大
22.2.5 字母表削減：引理22.6的證明
22.3 2cspw的難度：鴻溝和字母表大小之間的平衡
22.3.1 萊斯的證明思想：并行重複
22.4 哈斯塔德3位pcp定理和max3sat的難度
22.4.1 max3sat的近似難度
22.5 工具：傅裡葉變換
22.5.1 gf(2)n上的傅裡葉變換
22.5.2 從較高層面看傅裡葉變換和pcp之間的聯系
22.5.3 gf(2)上線性測試的分析
22.6 坐标函數、長編碼及其測試
22.7 定理22.16的證明
22.8 setcover的近似難度
22.9 其他pcp定理概述
22.9.1 具有亞常數可靠性參數的pcp定理
22.9.2 平攤的查驗複雜度
22.9.3 2位測試和高效傅裡葉分析
22.9.4 唯一性遊戲和門檻值結果
22.9.5 與等周問題和度量空間嵌入之間的聯系
22.a 将qcsp執行個體轉換成“精細”執行個體
第23章 為什麼線路下界如此困難
23.1 自然證明的定義
23.2 為什麼自然證明是自然的
23.2.1 為什麼要求可構造性
23.2.2 為什麼要求廣泛性
23.2.3 用複雜性測度看自然證明
23.3 定理23.1的證明
23.4 一個“不自然的”下界
23.5 哲學觀點
附錄a 數學基礎
部分習題的提示
參考文獻
術語索引
複雜性類索引
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)