齣版者的話
譯者序
譯者簡介
前言
緻謝
引言
第0章記號約定1
0.1對象的字符串錶示1
0.2判定問題／語言2
0.3大O記號2
習題3
第一部分基本復雜性類
第1章計算模型——為什麼模型選擇無關緊要6
1.1計算的建模：你真正需要瞭解的內容6
1.2圖靈機7
1.2.1圖靈機的錶達能力10
1.3效率和運行時間11
1.3.1定義的健壯性11
1.4機器的位串錶示和通用圖靈機14
1.4.1通用圖靈機14
1.5不可計算性簡介15
1.5.1停機問題16
1.5.2哥德爾定理17
1.6類P18
1.6.1為什麼模型選擇無關緊要19
1.6.2P的哲學意義19
1.6.3P的爭議和解決爭議的一些努力20
1.6.4埃德濛茲的引言21
1.7定理1.9的證明：O（TlogT）時間的通用模擬21
本章學習內容24
本章注記和曆史24
習題26
第2章NP和NP完全性29
2.1類NP29
2.1.1P和NP的關係31
2.1.2非確定型圖靈機31
2.2歸約和NP完全性32
2.3庫剋勒維定理：計算的局部性34
2.3.1布爾公式、閤取範式和SAT問題34
2.3.2庫剋勒維定理34
2.3.3準備工作：布爾公式的錶達能力35
2.3.4引理2.11的證明35
2.3.5將SAT歸約到3SAT38
2.3.6深入理解庫剋勒維定理38
2.4歸約網絡39
2.5判定與搜索42
2.6coNP、EXP和NEXP43
2.6.1coNP43
2.6.2EXP和NEXP44
2.7深入理解P、NP及其他復雜性類45
2.7.1NP的哲學意義45
2.7.2NP與數學證明45
2.7.3如果P=NP會怎樣45
2.7.4如果NP=coNP會怎樣46
2.7.5NP和NP完全之間存在其他復雜性類嗎47
2.7.6NP難的處理47
2.7.7更精細的時間復雜性48
本章學習內容48
本章注記和曆史48
習題49
第3章對角綫方法53
3.1時間分層定理53
3.2非確定型時間分層定理54
3.3拉德納爾定理：NP非完全問題的存在性55
3.4神喻機器和對角綫方法的局限性57
3.4.1邏輯獨立與相對59
本章學習內容59
本章注記和曆史59
習題60
第4章空間復雜性61
4.1空間受限計算的定義61
4.1.1格局圖62
4.1.2一些空間復雜性類63
4.1.3空間分層定理64
4.2PSPACE完全性64
4.2.1塞維奇定理67
4.2.2PSPACE的本質：最佳博弈策略67
4.3NL完全性68
4.3.1基於證明的NL定義：僅能讀一次的證明70
4.3.2NL=coNL71
本章學習內容72
本章注記和曆史73
習題73
第5章多項式分層和交錯75
5.1類Σp275
5.2多項式分層76
5.2.1多項式分層的性質76
5.2.2PH各層的完全問題77
5.3交錯圖靈機78
5.3.1無限次交錯79
5.4時間與交錯：SAT的時空平衡79
5.5用神喻圖靈機定義多項式分層80
本章學習內容81
本章注記和曆史81
習題82
第6章布爾綫路83
6.1布爾綫路和P／poly83
6.1.1P／poly和P之間的關係85
6.1.2綫路的可滿足性和庫剋勒維定理的另一種證明86
6.2一緻綫路87
6.2.1對數空間一緻綫路族87
6.3納言圖靈機88
6.4P／poly和NP88
6.5綫路下界89
6.6非一緻分層定理90
6.7綫路復雜性類的精細分層91
6.7.1類NC和類AC92
6.7.2P完全性92
6.8指數規模的綫路93
本章學習內容93
本章注記和曆史94
習題94
第7章隨機計算96
7.1概率型圖靈機97
7.2概率型圖靈機示例98
7.2.1尋找中位數99
7.2.2概率型素性測試100
7.2.3多項式恒等測試101
7.2.4二分圖的完美匹配測試102
7.3單麵錯誤和“零麵”錯誤：RP、coRP、ZPP103
7.4定義的健壯性103
7.4.1準確度常數的作用：錯率歸約104
7.4.2期望運行時間與最壞運行時間105
7.4.3使用比均勻硬幣投擲更具一般性的隨機選擇106
7.5BPP同其他復雜性類之間的關係106
7.5.1BPPP／poly107
7.5.2BPPPH107
7.5.3分層定理與完全問題108
7.6隨機歸約109
7.7空間受限的隨機計算109
本章學習內容110
本章注記和曆史110
習題111
第8章交互式證明113
8.1交互式證明及其變形113
8.1.1準備工作：驗證者和證明者均為確定型的交互式證明113
8.1.2類IP：概率型驗證者115
8.1.3圖不同構的交互式證明116
8.2公用隨機源和類AM118
8.2.1私有隨機源的模擬119
8.2.2集閤下界協議120
8.2.3定理8.12的證明概要123
8.2.4GI能是NP完全的嗎123
8.3IP=PSPACE124
8.3.1算術化125
8.3.2#SATD的交互式協議125
8.3.3TQBF的協議：定理8.19的證明127
8.4證明者的能力128
8.5多證明者交互式證明129
8.6程序檢驗130
8.6.1具有驗證程序的語言131
8.6.2隨機自歸約與積和式131
8.7積和式的交互式證明132
8.7.1協議133
本章學習內容134
本章注記和曆史134
習題135
第9章密碼學137
9.1完全保密及其局限性138
9.2計算安全、單嚮函數和僞隨機數産生器139
9.2.1單嚮函數：定義和實例141
9.2.2用單嚮函數實現加密142
9.2.3僞隨機數産生器143
9.3用單嚮置換構造僞隨機數産生器144
9.3.1不可預測性蘊含僞隨機性144
9.3.2引理9.10的證明：戈德賴希勒維定理145
9.4零知識149
9.5應用151
9.5.1僞隨機函數及其應用151
9.5.2去隨機化153
9.5.3電話投幣和比特承諾154
9.5.4安全的多方計算154
9.5.5機器學習的下界155
本章學習內容155
本章注記和曆史155
習題158
第10章量子計算161
10.1量子怪相：雙縫實驗162
10.2量子疊加和量子位163
10.2.1EPR悖論165
10.3量子計算的定義和BQP168
10.3.1綫性代數預備知識168
10.3.2量子寄存器及其狀態嚮量168
10.3.3量子操作169
10.3.4量子操作實例169
10.3.5量子計算與BQP171
10.3.6量子綫路172
10.3.7傳統計算是量子計算的特例173
10.3.8通用操作173
10.4格羅弗搜索算法174
10.5西濛算法177
10.5.1定理10.14的證明177
10.6肖爾算法：用量子計算機實現整數分解178
10.6.1ZM上的傅裏葉變換179
10.6.2ZM上的量子傅裏葉變換180
10.6.3肖爾的階發現算法181
10.6.4因數分解歸約為階發現184
10.6.5實數的有理數近似185
10.7BQP和經典復雜性類186
10.7.1量子計算中類似於NP和AM的復雜性類187
本章學習內容187
本章注記和曆史188
習題190
第11章PCP定理和近似難度簡介192
11.1動機：近似求解NP難的優化問題193
11.2用兩種觀點理解PCP定理194
11.2.1PCP定理與局部可驗證明194
11.2.2PCP定理與近似難度197
11.3兩種觀點的等價性197
11.3.1定理11.5與定理11.9的等價性198
11.3.2重新審視PCP的兩種理解199
11.4頂點覆蓋問題和獨立集問題的近似難度200
11.5NPPCP（poly（n），1）：由沃爾什哈達瑪編碼得到的PCP202
11.5.1綫性測試與沃爾什哈達瑪編碼202
11.5.2定理11.19的證明203
本章學習內容206
本章注記和曆史206
習題207
第二部分具體計算模型的下界
第12章判定樹210
12.1判定樹和判定樹復雜性210
12.2證明復雜性212
12.3隨機判定樹213
12.4證明判定樹下界的一些技術214
12.4.1隨機復雜性的下界214
12.4.2敏感性215
12.4.3次數方法216
本章學習內容217
本章注記和曆史217
習題218
第13章通信復雜性219
13.1雙方通信復雜性的定義219
13.2下界方法220
13.2.1詐集方法220
13.2.2鋪砌方法221
13.2.3秩方法222
13.2.4差異方法223
13.2.5證明差異上界的一種技術223
13.2.6各種下界方法的比較224
13.3多方通信復雜性225
13.4其他通信復雜性模型概述227
本章學習內容228
本章注記和曆史228
習題229
第14章綫路下界：復雜性理論的滑鐵盧232
14.1AC0和哈斯塔德開關引理232
14.1.1哈斯塔德開關引理233
14.1.2開關引理的證明234
14.2帶“計數器”的綫路：ACC236
14.3單調綫路的下界239
14.3.1定理14.7的證明239
14.4綫路復雜性的前沿242
14.4.1用對角綫方法證明綫路下界242
14.4.2ACCVsP的研究現狀243
14.4.3具有對數深度的綫性綫路244
14.4.4綫路圖244
14.5通信復雜性方法245
14.5.1與ACCO綫路之間的聯係245
14.5.2與綫性規模對數深度的綫路之間的聯係246
14.5.3與綫路圖之間的聯係246
14.5.4卡奇梅爾維格德爾森通信遊戲
與深度下界246
本章學習內容248
本章注記和曆史249
習題249
第15章證明復雜性251
15.1幾個例子251
15.2命題演算與歸結252
15.2.1用瓶頸法證明下界253
15.2.2插值定理和歸結的指數下界254
15.3其他證明係統概述256
15.4元數學的思考258
本章學習內容258
本章注記和曆史258
習題259
第16章代數計算模型260
16.1代數直綫程序和代數綫路261
16.1.1代數直綫程序261
16.1.2例子262
16.1.3代數綫路263
16.1.4代數綫路中類似於P、NP的復雜性類264
16.2代數計算樹266
16.2.1下界的拓撲方法268
16.3布盧姆舒布斯梅爾模型270
16.3.1復數上的復雜性類271
16.3.2完全問題和希爾伯特零點定理271
16.3.3判定性問題——曼德勃羅集272
本章學習內容272
本章注記和曆史273
習題274
第三部分高級專題
第17章計數復雜性278
17.1計數問題舉例278
17.1.1計數問題與概率估計279
17.1.2計數可能難於判定279
17.2復雜性類#P280
17.2.1復雜性類PP：類似於#P的判定問題281
17.3#P完全性281
17.3.1積和式和瓦利安特定理282
17.3.2#P問題的近似解286
17.4戶田定理：PHP#SAT287
17.4.1過渡：具有唯一解的布爾滿足性問題288
17.4.2⊕的性質和對NP、coNP證明引理17.17289
17.4.3引理17.17的證明：一般情形290
17.4.4第二步：轉換為確定型歸約291
17.5待決問題292
本章學習內容293
本章注記和曆史293
習題293
第18章平均復雜性：勒維定理295
18.1分布問題與distP296
18.2“實際分布”的形式化定義298
18.3distNP及其完全問題298
18.3.1distNP的一個完全問題300
18.3.2P可抽樣的分布301
18.4哲學意義和實踐意義301
本章學習內容303
本章注記和曆史303
習題303
第19章難度放大和糾錯碼305
19.1從溫和難度到強難度：姚期智XOR引理306
19.1.1用因帕利亞佐難度核引理證明姚期智XOR引理307
19.1.2因帕利亞佐難度核引理的證明309
19.2工具：糾錯碼310
19.2.1顯式糾錯碼312
19.2.2沃爾什哈達瑪糾錯碼312
19.2.3裏德所羅門糾錯碼313
19.2.4裏德穆勒糾錯碼313
19.2.5拼接糾錯碼314
19.3高效解碼315
19.3.1裏德所羅門解碼315
19.3.2拼接解碼316
19.4局部解碼與難度放大316
19.4.1沃爾什哈達瑪糾錯碼的局部解碼算法318
19.4.2裏德穆勒糾錯碼的局部解碼算法318
19.4.3拼接糾錯碼的局部解碼算法319
19.4.4局部解碼算法綜閤運用於難度放大320
19.5列錶解碼321
19.5.1裏德所羅門糾錯碼的列錶解碼322
19.6局部列錶解碼：接近BPP=P323
19.6.1沃爾什哈達瑪糾錯碼的局部列錶解碼323
19.6.2裏德穆勒糾錯碼的局部列錶解碼323
19.6.3拼接糾錯碼的局部列錶解碼325
19.6.4局部列錶解碼算法綜閤運用於難度放大325
本章學習內容326
本章注記和曆史327
習題328
第20章去隨機化330
20.1僞隨機數産生器和去隨機化331
20.1.1用僞隨機數産生器實現去隨機化331
20.1.2難度與去隨機化333
20.2定理20.6的證明：尼散維格德爾森構造334
20.2.1兩個示意性例子334
20.2.2尼散維格德爾森構造336
20.3一緻假設下的去隨機化339
20.4去隨機化需要綫路下界340
本章學習內容343
本章注記和曆史343
習題344
第21章僞隨機構造：擴張圖和提取器345
21.1隨機遊走和特徵值346
21.1.1分布嚮量和參數λ（G）346
21.1.2無嚮連通性問題的隨機算法的分析349
21.2擴張圖349
21.2.1代數定義350
21.2.2組閤擴張和擴張圖的存在性350
21.2.3代數擴張圖蘊含組閤擴張圖351
21.2.4組閤擴張圖蘊含代數擴張圖352
21.2.5用擴張圖設計糾錯碼353
21.3擴張圖的顯式構造355
21.3.1鏇轉映射356
21.3.2矩陣乘積和路徑乘積356
21.3.3張量積356
21.3.4替換乘積357
21.3.5顯式構造359
21.4無嚮連通性問題的確定型對數空間算法361
21.4.1連通性問題的對數空間算法（定理21.21的證明）361
21.5弱隨機源和提取器362
21.5.1最小熵363
21.5.2統計距離364
21.5.3隨機性提取器的定義364
21.5.4提取器的存在性證明364
21.5.5基於哈希函數構造提取器365
21.5.6基於擴張圖的隨機遊走構造提取器366
21.5.7由僞隨機數産生器構造提取器366
21.6空間受限計算的僞隨機數産生器368
本章學習內容372
本章注記和曆史372
習題374
第22章PCP定理的證明和傅裏葉變換技術378
22.1非二進製字母錶上的約束滿足問題378
22.2PCP定理的證明379
22.2.1PCP定理的證明思路379
22.2.2迪納爾鴻溝放大：引理22.5的證明380
22.2.3擴張圖、隨機遊走和INDSET的近似難度381
22.2.4迪納爾鴻溝放大382
22.2.5字母錶削減：引理22.6的證明387
22.32CSPW的難度：鴻溝和字母錶大小之間的平衡389
22.3.1萊斯的證明思想：並行重復389
22.4哈斯塔德3位PCP定理和MAX3SAT的難度390
22.4.1MAX3SAT的近似難度390
22.5工具：傅裏葉變換391
22.5.1GF（2）n上的傅裏葉變換391
22.5.2從較高層麵看傅裏葉變換和PCP之間的聯係393
22.5.3GF（2）上綫性測試的分析393
22.6坐標函數、長編碼及其測試395
22.7定理22.16的證明396
22.8SETCOVER的近似難度400
22.9其他PCP定理概述402
22.9.1具有亞常數可靠性參數的PCP定理402
22.9.2平攤的查驗復雜度402
22.9.32位測試和高效傅裏葉分析403
22.9.4唯一性遊戲和閾值結果404
22.9.5與等周問題和度量空間嵌入之間的聯係404
22.A將qCSP實例轉換成“精細”實例405
本章學習內容406
本章注記和曆史407
習題408
第23章為什麼綫路下界如此睏難411
23.1自然證明的定義411
23.2為什麼自然證明是自然的412
23.2.1為什麼要求可構造性413
23.2.2為什麼要求廣泛性413
23.2.3用復雜性測度看自然證明414
23.3定理23.1的證明415
23.4一個“不自然的”下界416
23.5哲學觀點417
本章注記和曆史417
習題418
附錄A數學基礎419
部分習題的提示438
參考文獻447
術語索引472
復雜性類索引478
· · · · · · (收起)