計算複雜性：現代方法 (Computational Complexity: A Modern Approach) 计算复杂性:现代方法

<內容簡介>

本書系統地介紹計算複雜性理論的經典結果和近30年來取得的新成果，旨在幫助讀者瞭解和掌握複雜性理論中的基本結果、思維方法、主要工具、研究前沿和待決問題。本書分為三部分。第一部分（第1～11章）較寬泛地介紹了複雜性理論，包括複雜性理論的經典結果和一些現代專題。第二部分（第12～16章）討論了各種具體計算模型上的計算複雜性下界。第三部分（第17～23章）主要是1980年以後人們在復雜性理論方面獲得的進展，內容包括計數複雜性、平均複雜性、難度放大、去隨機化和偽隨機性、PCP定理的證明以及自然證明。本書內容豐富，結構靈活，語言流暢，是從事計算複雜性理論及相關領域的研究人員必不可少的參考書，非常適合作為打算進入該研究領域的研究生、博士生快速接觸研究前沿的參考資料，還非常適合作為普通高校計算機科學與技術、數學專業本科生、研究生相關課程的教材，其中的高級專題還可以作為博士生相關討論班的素材。

<章節目錄>

出版者的話
譯者序
譯者簡介
前言
致謝
引言
第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

<作者介紹>

作者：（美國）桑傑夫·阿羅拉（Sanjeev Arora） （美國）博阿茲·巴拉克（Boaz Barak） 譯者：駱吉洲