鏈接：https://pan.baidu.com/s/1UmCIAmSLnAN6l9rv5CC0wg?pwd=x8dz?

提取碼：x8dz

本書(shū)是一本介紹計(jì)算復(fù)雜性理論的基礎(chǔ)教材, 內(nèi)容括時(shí)間復(fù)雜性、空間復(fù)雜性、NP-理論、多項(xiàng)式譜

系、電路復(fù)雜性、隨機(jī)計(jì)算及去隨機(jī)、計(jì)數(shù)復(fù)雜性、交互證明系統(tǒng)、PCP 定理、近似計(jì)算與不可近似性。



本書(shū)的主要讀者群是高年級(jí)本科生、碩士生、博士生，以及希望了解（更多）計(jì)算復(fù)雜性理論的教師

和科研工作者。本書(shū)可用于以下課程：（1）面向高年級(jí)本科生、研究生的“計(jì)算復(fù)雜性理論導(dǎo)論”課程，

內(nèi)容涵蓋前3 章；（2）面向研究生的“計(jì)算復(fù)雜性理論高等議題”課程，內(nèi)容涵蓋后3 章；（3）面向高年

級(jí)本科生、研究生的“算法理論”課程，涵蓋第 4 章、第 6 章中有關(guān)隨機(jī)算法和去隨機(jī)、近似算法和不

可近似性的內(nèi)容；（4）面向高年級(jí)本科生、研究生的“計(jì)算理論”課程，以第 1 章的內(nèi)容為核心，并根

據(jù)學(xué)分多少和授課對(duì)象不同做適當(dāng)補(bǔ)充。

第 1 章 計(jì)算理論 ?1
1.1 圖靈機(jī) ?5
1.2 時(shí)間可構(gòu)造性 9
1.3 通用圖靈機(jī) ?10
1.4 對(duì)角線方法 ?15
1.5 丘奇-圖靈論題 17
1.6 加速定理 21
1.7 時(shí)間復(fù)雜性類(lèi) ?24
1.8 非確定圖靈機(jī) ?26
1.9 命題邏輯 29
1.10 謂詞邏輯 32
1.11 計(jì)算的邏輯刻畫(huà) 34
1.12 時(shí)間譜系定理 ?37
1.13 間隙定理 41
1.14 諭圖靈機(jī) 42
1.15 歸約 ?43
1.16 空間復(fù)雜性類(lèi) ?45
1.17 對(duì)數(shù)空間類(lèi) 49
1.18 多項(xiàng)式空間類(lèi) ?52
1.19 對(duì)數(shù)空間的補(bǔ)封閉性 ?55
1.20 TIME(T(n))=SPACE(T(n)) 嗎 ?58
第 1 章練 63
第 2 章 難解性 ?65
2.1 可驗(yàn)證性 66
2.2 NP-完全性 ?68
2.3 庫(kù)克-萊文定理 69
2.4 拉德納定理 ?73
2.5 貝克-吉爾-索羅維定理 76
2.6 多項(xiàng)式譜系 ?78
2.7 譜系的邏輯刻畫(huà) ?80
2.8 譜系的交替機(jī)刻畫(huà) 82
2.9 無(wú)限譜系假設(shè) ?86
2.10 第二層中的完全問(wèn)題 ?87
第 2 章練 91
第 3 章 電路復(fù)雜性 93
3.1 電路譜系定理 ?96
3.2 一電路 101
3.3 P/poly ?103
3.4 并行計(jì)算 105
3.5 P-完全性 109
3.6 哈斯塔德對(duì)換引理 ?111
第 3 章練 ?117
第 4 章 隨機(jī)計(jì)算與去隨機(jī) ?119
4.1 隨機(jī)算法 121
4.2 通用哈希函數(shù)族 136
4.3 概率圖靈機(jī) 139
4.4 BPP 與 ZPP 141
4.5 PP 與 #P 146
4.6 積和式計(jì)算 151
4.7 戶田定理 155
4.8 隨機(jī)游走 159
4.9 蒙卡羅方法 ?172
4.9.1 近似采樣 ?175
4.9.2 馬爾可夫鏈蒙卡羅方法 ?185
4.9.3 均混時(shí)間 ?188
4.10 擴(kuò)張圖與去隨機(jī) 195
4.10.1 線性代數(shù)相關(guān)知識(shí) ?196
4.10.2 圖的譜 200
4.10.3 擴(kuò)張圖 207
4.10.4 擴(kuò)張圖上的隨機(jī)游走 215
4.11 擴(kuò)張圖的構(gòu)造 ?219
4.11.1 擴(kuò)張圖的構(gòu)造算子 ?220
4.11.2 固定大小擴(kuò)張圖構(gòu)造 226
4.11.3 顯式擴(kuò)張圖族 ?228
4.12 萊因戈?duì)柕露ɡ?231
第 4 章練 ?234
第 5 章 交互證明系統(tǒng) ?236
5.1 私幣交互證明 ?239
5.2 公幣交互證明 ?244
5.3 IP = PSPACE ?252
5.4 兩類(lèi)系統(tǒng)的等性 ?257
5.5 多證明者交互證明系統(tǒng) ?262
5.5.1 定義 ?263
5.5.2 NEXP 的多證明者協(xié)議 ?268
5.6 多線性性測(cè)試算法 ?273
5.7 并行重復(fù)定理 ?279
5.7.1 統(tǒng)計(jì)距離、詹森不等式、相對(duì)熵 282
5.7.2 隨機(jī)變量的近似嵌入 289
5.7.3 博弈的近似生成 293
5.7.4 證明的后一步 297
5.8 單回合雙證明者交互系統(tǒng) 298
第 5 章練 ?302
第 6 章 近似計(jì)算與不可近似性 ?304
6.1 近似算法 307
6.2 不可近似性 324
6.3 局可驗(yàn)證性與不可近似性 ?327
6.4 錯(cuò)誤放大 331
6.5 證明思想 334
6.6 線性增強(qiáng) 339
6.7 線性歸減 343
6.8 PCP 定理的證明 345
6.9 布爾函數(shù)的分析技術(shù) ?346
6.9.1 傅里葉展開(kāi)式 ?348
6.9.2 卷積定理 ?350
6.9.3 BLR-測(cè)試 ?351
6.9.4 長(zhǎng)碼 ?353
6.10 哈斯塔德 3-比 PCP-定理 357
6.10.1 哈斯塔德驗(yàn)證器 359
6.10.2 哈斯塔德算法的可靠性 ?361
6.11 閾值定理 ?364
第 6 章練 ?369
參考文獻(xiàn) 370
定理索引 371
圖索引 373
術(shù)語(yǔ)索引 374