具體描述
編輯推薦
計算復雜性理論的研究是計算機科學重要的研究領域之一，而Chistos H. Papadimitriou是該領域知名的專傢之一。
計算復雜性是計算機科學中思考為什麼有些問題用計算機難以解決的領域，是理論計算機科學研究的重要內容。復雜性是計算（復雜性類）和應用（問題）之間復雜而核心的部分。
本書是一本全麵闡述計算復雜性理論及其近年來進展的教科書，內容頗為深奧，重點介紹復雜性的計算、問題和邏輯。本書主要內容包含算法圖靈機、可計算性等有關計算復雜性理論的基本概念；布爾邏輯、一階邏輯、邏輯中的不可判定性等復雜性理論的基礎知識；P與NP、NP完全等各復雜性類的概念及其之間的關係等復雜性理論的核心內容；隨機算法、近似算法、並行算法及其復雜性理論；以及NP之外（如多項式空間等）復雜性類的介紹。每章最後一節包括相關的參考文獻、注解、練習和問題，很多問題涉及更深的結論和研究。
內容簡介
《計算復雜性：現代方法》係統地介紹計算復雜性理論的經典結果和近30年來取得的新成果，旨在幫助讀者瞭解和掌握復雜性理論中的基本結果、思維方法、主要工具、研究前沿和待決問題。本書分為三部分。*部分（第1～11章）較寬泛地介紹瞭復雜性理論，包括復雜性理論的經典結果和一些現代專題。第二部分（第12～16章）討論瞭各種具體計算模型上的計算復雜性下界。第三部分（第17～23章）主要是1980年以後人們在復雜性理論方麵獲得的進展，內容包括計數復雜性、平均復雜性、難度放大、去隨機化和僞隨機性、PCP定理的證明以及自然證明。本書內容豐富，結構靈活，語言流暢，是從事計算復雜性理論及相關領域的研究人員必不可少的參考書，非常適閤作為打算進入該研究領域的研究生、博士生快速接觸研究前沿的參考資料，還非常適閤作為普通高校計算機科學與技術、數學專業本科生、研究生相關課程的教材，其中的高級專題還可以作為博士生相關討論班的素材。
作者簡介
剋裏斯特斯 H. 帕帕季米特裏烏（Christos H. Papadimitriou），是當今計算機科學界最活躍和有影響力的科學傢之一。Papadimitriou擁有普林斯頓大學博士學位，現為加州大學伯剋利分校計算機科學係教授。他曾在哈佛大學、麻省理工學院、雅典工藝大學、斯坦福大學、加州大學聖地亞哥分校任教。他是美國科學院院士、美國工程院院士和美國人文科學院院士。他於2002年獲得高德納奬，2012年獲得哥德爾奬。他的主要研究領域是算法和復雜性，以及它們在優化、數據庫、人工智能、經濟和互聯網等方麵的應用，曾撰寫此領域教科書5本，發錶論文數篇。
目錄
齣版者的話
譯者序
譯者簡介
前言
緻謝
引言
第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.2 P的哲學意義19
1.6.3 P的爭議和解決爭議的一些努力20
1.6.4 埃德濛茲的引言21
1.7 定理1.9的證明：O(TlogT)時間的通用模擬21
本章學習內容24
本章注記和曆史24
習題26
第2章 NP和NP完全性29
2.1 類NP29
2.1.1 P和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.6 coNP、EXP和NEXP43
2.6.1 coNP43
2.6.2 EXP和NEXP44
2.7 深入理解P、NP及其他復雜性類45
2.7.1 NP的哲學意義45
2.7.2 NP與數學證明45
2.7.3 如果P=NP會怎樣45
2.7.4 如果NP=coNP會怎樣46
2.7.5 NP和NP完全之間存在其他復雜性類嗎47
2.7.6 NP難的處理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.2 PSPACE完全性64
4.2.1 塞維奇定理67
4.2.2 PSPACE的本質：*佳博弈策略67
4.3 NL完全性68
4.3.1 基於證明的NL定義:僅能讀一次的證明70
4.3.2 NL=coNL71
本章學習內容72
本章注記和曆史73
習題73
第5章 多項式分層和交錯75
5.1 類Σp275
5.2 多項式分層76
5.2.1 多項式分層的性質76
5.2.2 PH各層的完全問題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.1 P/poly和P之間的關係85
6.1.2 綫路的可滿足性和庫剋勒維定理的另一種證明86
6.2 一緻綫路87
6.2.1 對數空間一緻綫路族87
6.3 納言圖靈機88
6.4 P/poly和NP88
6.5 綫路下界89
6.6 非一緻分層定理90
6.7 綫路復雜性類的精細分層91
6.7.1 類NC和類AC92
6.7.2 P完全性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.5 BPP同其他復雜性類之間的關係106
7.5.1 BPP�罰/poly107
7.5.2 BPP�罰H107
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.4 GI能是NP�餐耆�的嗎123
8.3 IP=PSPACE124
8.3.1 算術化125
8.3.2 #SATD的交互式協議125
8.3.3 TQBF的協議：定理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.1 EPR悖論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.1 ZM上的傅裏葉變換179
10.6.2 ZM上的量子傅裏葉變換180
10.6.3 肖爾的階發現算法181
10.6.4 因數分解歸約為階發現184
10.6.5 實數的有理數近似185
10.7 BQP和經典復雜性類186
10.7.1 量子計算中類似於NP和AM的復雜性類187
本章學習內容187
本章注記和曆史188
習題190
第11章 PCP定理和近似難度簡介192
11.1 動機：近似求解NP難的優化問題193
11.2 用兩種觀點理解PCP定理194
11.2.1 PCP定理與局部可驗證明194
11.2.2 PCP定理與近似難度197
11.3 兩種觀點的等價性197
11.3.1 定理11.5與定理11.9的等價性198
11.3.2 重新審視PCP的兩種理解199
11.4 頂點覆蓋問題和獨立集問題的近似難度200
11.5 NP�罰CP(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.1 AC0和哈斯塔德開關引理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.2 ACC Vs P的研究現狀243
14.4.3 具有對數深度的綫性綫路244
14.4.4 綫路圖244
14.5 通信復雜性方法245
14.5.1 與ACC0綫路之間的聯係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�罰#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.3 distNP及其完全問題298
18.3.1 distNP的一個完全問題300
18.3.2 P�部沙檠�的分布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.2 PCP定理的證明379
22.2.1 PCP定理的證明思路379
22.2.2 迪納爾鴻溝放大：引理22.5的證明380
22.2.3 擴張圖、隨機遊走和INDSET的近似難度381
22.2.4 迪納爾鴻溝放大382
22.2.5 字母錶削減：引理22.6的證明387
22.3 2CSPW的難度：鴻溝和字母錶大小之間的平衡389
22.3.1 萊斯的證明思想：並行重復389
22.4 哈斯塔德3位PCP定理和MAX��3SAT的難度390
22.4.1 MAX��3SAT的近似難度390
22.5 工具：傅裏葉變換391
22.5.1 GF(2)n上的傅裏葉變換391
22.5.2 從較高層麵看傅裏葉變換和PCP之間的聯係393
22.5.3 GF(2)上綫性測試的分析393
22.6 坐標函數、長編碼及其測試395
22.7 定理22.16的證明396
22.8 SET�睠OVER的近似難度400
22.9 其他PCP定理概述402
22.9.1 具有亞常數可靠性參數的PCP定理402
22.9.2 平攤的查驗復雜度402
22.9.3 2位測試和高效傅裏葉分析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
精彩書摘
《計算復雜性：現代方法》：本章注記和曆史
量子計算機是可逆的（引理10.7）。在開始著手研究量子計算之前，人們曾對可逆計算這一領域開展瞭研究（Ben87）。可逆計算旨在從熱力學角度找齣傳統計算機計算速度的局限性。Toffoli門正是在這樣的背景下被提齣的。
1982年，費曼（Fey82）指齣，在傳統的圖靈機上似乎無法高效地模擬量子力學，並建議建立量子計算機來執行這種模擬。（事實上，如果量子計算機真的被建造齣來，則它的主要應用也就是模擬傳統計算機。）同時，費曼還指齣，量子圖靈機的計算能力可能會強於傳統圖靈機。1985年，德吾奇（Deutsch）首先形式地定義瞭量子圖靈機，雖然現在看來他的定義不盡令人滿意。後來，更完善的定義齣現在德吾奇，約薩（Josza）的論文（DJ92）和伯恩斯坦（Bernstein），瓦茲拉尼（Vazirani）的論文（BV93）中。後一篇論文首次證明瞭通用量子圖靈機的存在性，並證明瞭用通用量子圖靈機模擬其他量子圖靈機時僅導緻計算效率下降一個多項式因子。姚期智（Ya093）將這些結果推廣到瞭量子綫路上，本章給齣的量子計算的定義源自姚期智。（與量子綫路相比，伯恩斯坦一瓦茲拉尼定義的量子圖靈機容忍噪音的能力較差，因此被認為是不太可能被實現的。）德吾奇（Deu89）證明瞭某個3量子門在量子綫路中是通用量子門，而索洛維（Solovay）（1995年未發錶的手稿）和基塔耶夫（Ki-taev）各自獨立地證明瞭，通用量子門可以將任意酉陣近似到量子門個數的指數精度，由此得到定理10.12（盡管本章錶述該定理時使用瞭書（NCOO）中提到的特殊通用基）。
……
前言/序言
Complexity，A Modern Approach計算復雜性理論在過去三十多年中發展迅速。自1990年以來取得的齣人意料的結果和基礎性的結果本身就可以寫齣一部書。這些結果涉及的領域非常廣泛，包括：經典復雜性類的概率型新定義（IP=PSPACE和各種PCP定理）以及它們在近似算法中的應用，肖爾（Shor）為量子計算機設計的整數因數分解算法，對人們目前處理著名的P?=NP問題� ∫胛撓謾癙?=NP”來錶示原文中的“P versus NP”。——譯者注�〉母髦址椒ㄎ�什麼未能獲得成功的理解，去隨機化理論和基於計算難度的僞隨機性，以及隨機性提取器和擴張圖等僞隨機對象的優美構造。
本書的目標就是為瞭在介紹復雜性理論經典結果的同時闡述近年來取得的新成果。寫作本書的齣發點是讓它既可以作為教科書使用，也可以作為自學的參考書使用。這意味著我們在寫作本書時必須兼顧廣泛的讀者。為實現這一目標，我們對全書進行瞭精心的設計。我們實際上還假設讀者不具備關於計算的任何背景而且隻具備附錄A中概述的*少數學背景。我們為本書提供瞭一個網站http://www.cs.princeton.edu/theory/complexity。網站上列齣瞭相關的輔助材料，包括用本書作為教材時的詳細教學計劃、全書各個章節的草稿，以及涵蓋相關主題的其他資源的超鏈接。全書始終強調各個概念在何種場閤下是有用的，以及為什麼這些概念要這樣定義。在一些關鍵的定義上，我們還用一些例子進行瞭闡釋。為瞭使行文流暢，我們力爭盡可能少地引用參考文獻。參考文獻的引用有兩種情況，其一是當前的結果用到瞭文獻中的標準術語，其二是我們覺得為特定的結果提供一些曆史信息將有助於闡明其動機和適用的場閤。每章末尾有一個單獨的注記小節，它簡明扼要地討論瞭更多的相關工作。當一個概念有多種定義時，我們會選擇相對簡單的定義；當一個結果有多種證明時，我們會選擇能證得更具一般性的結論或者*優結論的證明。
全書分為三個部分。
�r第一部分：基本復雜性類。這個部分是對復雜性理論的廣泛介紹。從圖靈機的定義和可計算理論的基本概念開始，這個部分涵蓋瞭各種基本的時間復雜性類和空間復雜性類，還包含瞭更現代的一些專題，包括概率算法、交互式證明、密碼學、量子計算機和PCP定理及其應用。
第二部分：具體計算模型的下界。這個部分討論在綫路和判定樹等具體計算模型上用算法求解各種計算任務所需的計算資源的下界。這些計算模型初看起來與圖靈機有很大的區彆，但更深入研究將得到它們與圖靈機之間的有趣的相互聯係。
第三部分：高級專題。這個部分主要是1980年以後人們在復雜性理論方麵獲得的進展。內容包括計數復雜性、平均復雜性、難度放大、去隨機化和僞隨機性、PCP定理的證明以及自然證明。
本書的每一章幾乎都可以單獨進行閱讀，但是第1章、第2章和第7章不能跳過。正是這種設計，使得本書可以適用於下麵各種不同的讀者。
物理學傢、數學傢和其他科學傢。這個讀者群對計算復雜性理論越來越感興趣，他們特彆感興趣的是那些高調的研究結果，例如肖爾算法(Shor algorithm)和*近取得的確定型素性測試算法。這個讀者群的知識儲備豐富，他們可以快速通讀第一部分，然後迅速進入第二部分和第三部分，也可以單獨閱讀各個章節並找到理解當前研究結果所需的每個知識點。
本身不從事計算復雜性理論研究的計算機科學傢。他們既可以用本書來自學，也可以將本書作為參考書，還可以用本書來講授本科生或研究生的計算理論或計算復雜性理論課程。
從事計算復雜性理論研究或者打算從事這種研究的任何人，包括教授和學生。本書講解*新研究結果和高級專題的詳細程度可以讓打算從事復雜性理論和相關領域研究的讀者具有充足的知識儲備。
本書可以作為如下幾類課程的教科書。
本科生的計算理論課程。很多計算機科學係都用西普賽爾(Sipser)的書［Sip96］來為本科生開設計算復雜性理論這門課。本書可以用作對西普賽爾的教材在一些更現代的專題上的補充，這些專題包括概率算法、密碼學和量子計算。相比於自動機理論和可計算理論的精細劃分，本科生可能會發現這些專題更能令人耳目一新。所需的數學背景是能夠比較自然地閱讀數學證明以及離散數學知識，這些知識通常涵蓋於“離散數學”或“計算機數學”等課程中，而目前多數計算機係都已經開設瞭這樣的課程。
為高年級本科生和新入學的研究生開設的計算復雜性導論課程。本書還可以用來為計算機科學專業的高年級本科生和新入學的研究生開設計算復雜性導論課程，以替代1994年帕帕迪米特裏奧(Papadimitriou)撰寫的教材［Pap94］（該書未包含很多*近的研究成果）。這門課程可以講授第一部分的多數專題，再零星地講授第二部分和第三部分的內容，並且假設學生具備瞭一定的算法知識和計算理論的知識。
研究生的計算復雜性課程。本書也可以作為研究生的計算復雜性課程的教材，以培養學生在復雜性理論或者算法和機器學習等相關領域開展研究的能力。這門課程可以用第一部分來復習基本知識，然後進入第二部分和第三部分的高級專題中。本書的內容多於一個學期的教學內容，網站上提供瞭這門課程的其他幾種教學大綱。
研究生討論班或高級課程。第二部分和第三部分中的各個獨立章節都可以用於復雜性理論的討論班和高級課程，比如關於去隨機化、PCP定理和下界的討論班或高級課程。
本書網站為這些課程提供瞭幾種教學計劃和素材。如果你在課程中采用瞭本書，我們樂意瞭解情況並得到你的反饋。我們要求你不要在網上發布本書習題的答案，這樣其他人纔可以用這些習題給學生留作業或齣考題。
在寫作本書的過程中，我們清醒地意識到我們不得不捨棄對一些重要結果的講述。我們希望本書對其他教材的大量引用有助於讀者的進一步閱讀。同時，我們還計劃對本書的網站進行周期性的更新，以幫助讀者瞭解和瀏覽他們感興趣的新結果。
*重要的是，我們希望通過本書將計算復雜性中激動人心的研究結果以及它們對其他學科的深刻影響傳遞給讀者。
讓我們一起為徹底解決P?=NP問題而努力吧！
緻 謝Computational Complexity，A Modern Approach我們對復雜性理論的理解是在與同行交流的過程中逐步形成的。我們從他們身上學到瞭太多的東西，要感謝的人也遠不止下麵提到的這些人。Boaz首先要感謝兩位導師Oded Goldreich和Avi Wigderson，是他們把他引入瞭理論計算機科學的世界並不斷影響他在這一領域的思想。
我們感謝Luca Trevisan，他（從8年前開始！）對本書的寫作提供瞭持續不斷的鼓勵，並為第一版草稿中若乾章節的撰寫提供瞭大量幫助。一些同行毅然地同意並審閱瞭本書部分章節的早期草稿，他們是：Scott Aaronson,Noga Alon,Paul Beame,Irit Dinur,Venkatesan Guruswami,Jonathan Katz,Valentine Kavanets,Subhash Khot,Jirˇí Matou�宔k,Klaus Meer,Or Meir,Moni Naor,Alexandre Pinto,Alexander Razborov,Oded Regev,Omer Reingold,Rosen Shaltiel,Madhu Sudan,Amnon Ta�睸hma,Iannis Tourlakis,Chris Umans,Salil Vadhan,Dieter van Melkebeek,Umesh Vazirani和Joachim von zur Gathen.特彆感謝Jirˇí、Or、Alexandre、Dieter和Iannis，他們對本書的很多章節給齣瞭具體而有用的評述。
很多人指齣瞭本書的拼寫錯誤和缺陷，他們給齣的評述幫助我們改進瞭文字質量，還有一些人迴答瞭我們在特定證明中提齣的問題或者給齣瞭相應的參考文獻。在此，一並對他們錶示感謝，他們是：Emre Akbas,Eric Allender,Djangir Babayev,Miroslav Balaz,Arnold Beckmann,Ido Ben�睧liezer,Siddharth Bhaskar,Goutam Biswas,Shreeshankar Bodas,Josh Bronson,Arkadev Chattopadhyay,Bernard Chazelle,Maurice Cochand,Nathan Collins,Tim Crabtree,Morten Dahl,Ronald de Wolf,Scott Diehl,Dave Dody,Alex Fabrikant,Michael Fairbank,Joan Feigenbaum,Lance Fortnow,Matthew Franklin,Rong Ge,Ali Ghodsi,Parikshit Gopanlan,Vipul Goyal,Stephen Harris,Johan H�zstad,Andre Hernich,Yaron Hirsch,Thomas Holenstein,Xiu Huichao,Moukarram Kabbash,Bart Kastermans,Joe Kilian,Tomer Kotek,Michal Koucy,Sebastian Kuhnert,Katrina LaCurts,Chang�瞁ook Lee,James Lee,John Lenz,Meena Mahajan,Mohammad Mahmoody�睪hidary,Shohei Matsuura,Mauro Mazzieri,John McCullough,Eric Miles,Shira Mitchell,Mohsen Momeni,Kamesh Munagala,Rolf Neidermeier,Robert Nowotniak,Taktin Oey,Toni Pitassi,Emily Pitler,Aaron Potechin, Manoj Prabhakaran,Yuri Pritykin,Anup Rao,Saikiran Rapaka,Nicola Rebagliati,Johan Richter,Ron Rivest,Sushant Sachdeva,Mohammad Sadeq Dousti,Rahul Santhanam,Cem Say,Robert Schweiker,Thomas Schwentick,Joel Seiferas,Jonah Sherman,Amir Shpilka,Yael Snir,Nikhil Srivastava,Thomas Starbird,Jukka Suomela,Elad Tsur,Leslie Valiant,Vijay Vazirani,Suresh Venkatasubramanisn,Justin Vincent�睩oglesong,Jirka Vomlel,Daniel Wichs,Avi Wigderson,Maier Willard,Roger Wolff,Jureg Wullschleger,Rui Xue,Jon Yard,Henry Yuen,Wu Zhanbin和Yi Zhang.謝謝你們！
毫無疑問，上述列錶仍有可能遺漏瞭這些年嚮我們的創作提供過幫助的人，我們對那些被遺漏的人錶示感謝和歉意。
本書用LATEX進行排版,為此特彆感謝Donald Knuth和Leslie Lamport。Stephen Boyd和Lieven Vanderberghe爽快地嚮我們提供瞭他們寫作《凸優化》一書時使用的LATEX宏定義。
*重要的是，感謝我們的傢人——Silvia、Nia、Rohan Arora和Ravit、Alma Barak。
Sanjeev要感謝父親，父親是他創作本書的源泉。
用戶評價
書質量不錯，內容還沒看
評分東西很好，快遞小哥非常給力！
評分書質量不錯，內容還沒看
評分翻譯的作品買來看下，感覺還是挺好的。人油齣的書還是挺好
評分挺好的，需要好好看
評分內容充實 東西不錯 物流很好
評分挺好的，需要好好看
評分不錯，挺好，速度超快，支持京東
評分京東買書，放心，書很值得讀，要花點時間，加油，努力！
相關圖書
![空間數據分析理論與實踐 [Spatial Data Analysis Theory And Practice] pdf epub mobi 電子書 下載](https://pic.qciss.net/10082505/rBEhWVMqvosIAAAAAAGJRhdCfMgAAKapgIKsYgAAYle632.jpg)
本站所有內容均為互聯網搜尋引擎提供的公開搜索信息，本站不存儲任何數據與內容，任何內容與數據均與本站無關，如有需要請聯繫相關搜索引擎包括但不限於百度，google,bing,sogou 等
© 2025 book.cndgn.com All Rights Reserved. 新城书站 版權所有