計算複雜性理論

第 1 章 計算理論  1 
1.1 圖靈機  5 
1.2 時間可構造性 9 
1.3 通用圖靈機  10 
1.4 對角線方法  15 
1.5 丘奇-圖靈論題 17 
1.6 加速定理 21 
1.7 時間複雜性類  24 
1.8 非確定圖靈機  26 
1.9 命題邏輯 29 
1.10 謂詞邏輯 32 
1.11 計算的邏輯刻畫 34 
1.12 時間譜系定理  37 
1.13 間隙定理 41 
1.14 神諭圖靈機 42 
1.15 歸約  43 
1.16 空間複雜性類  45 
1.17 對數空間類 49 
1.18 多項式空間類  52 
1.19 對數空間的補封閉性  55 
1.20 TIME(T(n))=SPACE(T(n)) 嗎  58 
第 1 章練習 63 

第 2 章 難解性  65 
2.1 可驗證性 66
2.2 NP-完全性  68 
2.3 庫克-萊文定理 69 
2.4 拉德納定理  73 
2.5 貝克-吉爾-索羅維定理 76 
2.6 多項式譜系  78 
2.7 譜系的邏輯刻畫  80 
2.8 譜系的交替機刻畫 82 
2.9 無限譜系假設  86 
2.10 第二層中的完全問題  87
第 2 章練習 91 

第 3 章 電路複雜性 93 
3.1 電路譜系定理  96 
3.2 一致電路 101 
3.3 P/poly  103 
3.4 平行計算 105 
3.5 P-完全性 109 
3.6 哈斯塔德對換引理  111 
第 3 章練習  117 

第 4 章 隨機計算與去隨機  119 
4.1 隨機演算法 121 
4.2 通用雜湊函數族 136 
4.3 概率圖靈機 139 
4.4 BPP 與 ZPP 141 
4.5 PP 與 #P 146 
4.6 積和式計算 151 
4.7 戶田定理 155 
4.8 隨機遊走 159 
4.9 蒙特卡羅方法  172 
4.9.1 近似採樣  175
4.9.2 瑪律可夫鏈蒙特卡羅方法  185 
4.9.3 均混時間  188 
4.10 擴張圖與去隨機 195 
4.10.1 線性代數相關知識  196 
4.10.2 圖的譜 200 
4.10.3 擴張圖 207 
4.10.4 擴張圖上的隨機遊走 215 
4.11 擴張圖的構造  219 
4.11.1 擴張圖的構造運算元  220 
4.11.2 固定大小擴張圖構造 226 
4.11.3 顯式擴張圖族  228 
4.12 萊因戈爾德定理 231 
第 4 章練習  234 

第 5 章 交互證明系統  236 
5.1 私幣交互證明  239 
5.2 公幣交互證明  244 
5.3 IP = PSPACE  252 
5.4 兩類系統的等價性  257 
5.5 多證明者交互證明系統  262 
5.5.1 定義  263 
5.5.2 NEXP 的多證明者協議  268 
5.6 多線性性測試演算法  273 
5.7 並行重複定理  279 
5.7.1 統計距離、詹森不等式、相對熵 282 
5.7.2 隨機變數的近似嵌入 289 
5.7.3 博弈的近似生成 293 
5.7.4 證明的最後一步 297 
5.8 單回合雙證明者交互系統 298 
第 5 章練習  302

第 6 章 近似計算與不可近似性  304 
6.1 近似演算法 307 
6.2 不可近似性 324 
6.3 局部可驗證性與不可近似性  327 
6.4 錯誤放大 331 
6.5 證明思想 334 
6.6 線性增強 339 
6.7 線性歸減 343 
6.8 PCP 定理的證明 345 
6.9 布耳函數的分析技術  346 
6.9.1 傅裡葉展開式  348 
6.9.2 卷積定理  350 
6.9.3 BLR-測試  351 
6.9.4 長碼  353 
6.10 哈斯塔德 3-比特 PCP-定理 357 
6.10.1 哈斯塔德驗證器 359 
6.10.2 哈斯塔德演算法的可靠性  361 
6.11 閾值定理  364 
第 6 章練習  369 
參考文獻 370 
定理索引 371 
圖索引 373 
術語索引 374