緒論 計算復雜性理論簡介 1 0.1 計算復雜性理論的首要問題 1 0.2 計算復雜性理論與算法理論的區別 1 0.3 計算理論及其組成 1 0.4 計算復雜性理論與密碼學的關系 2 第1章 計算模型——Turing機 3 1.1 常用術語和記號 3 1.2 Turing機 4 1.2.1 Turing機的基本模型 4 1.2.2 TM的形式化定義 5 1.2.3 TM的格局 5 1.2.4 TM舉例 6 1.2.5 描述TM的不同方式 7 1.3 TM的穩健性 8 1.4 ChurchTuring命題 9 1.5 非確定性TM 10 1.6 通用TM 12 習題 12 第2章 計算任務與復雜性 13 2.1 關心的計算任務：判定語言 13 2.2 復雜性的度量 14 2.2.1 大O小o記號 15 2.2.2 時間/空間復雜性的定義 15 2.2.3 兩個事實 17 2.2.4 采用大O記號的合理性——帶壓縮定理和線性加速定理 17 2.2.5 帶數目的減少對時間復雜度和空間復雜度的影響 19 2.2.6 DTM與NDTM的時間復雜性關系 20 2.3 復雜性類 20 2.3.1 復雜性類的概念 20 2.3.2 TIME和SPACE之間的平凡(trivial)關系 21 習題 21 第3章 P與NP 23 3.1 P 類 23 3.1.1 P的定義 23 3.1.2 P的重要性 23 3.1.3 P中的問題 24 3.2 NP 類 25 3.2.1 NP的定義 25 3.2.2 NP中的問題 26 3.2.3 世紀難題 P =? NP 27 3.2.4 NP的等價定義 28 3.3 coNP與coNP=? NP 29 習題 31 第4章 歸約與NP完全性 32 4.1 歷史背景 32 4.2 歸約 32 4.2.1 Cook歸約 32 4.2.2 Karp歸約 33 4.2.3 Levin歸約 34 4.3 NP完全性 35 4.4 CookLevin定理 36 4.5 更多NP完全問題 40 4.6 其他NPC問題 43 習題 44 第5章 關于P和NP的更多知識 46 5.1 查找與判定：NPC問題的自歸約特性 46 5.1.1 SAT的自歸約特性 46 5.1.2 CLIQUE的自歸約特性 47 5.1.3 NPC問題都滿足自歸約特性 48 5.2 NPI語言 49 5.3 P vs NP 50 5.3.1 哈密爾頓回路vs 歐拉回路 50 5.3.2 三色vs四色 51 5.3.3 3SAT vs 2SAT 51 5.4 Oracle TM——相對化 54 習題 56 第6章 對角化方法 57 6.1 對角化方法與不可判定問題的存在性 57 6.1.1 可數集與對角化方法 57 6.1.2 不可判定問題的存在性 58 6.1.3 停機問題不可判定 60 6.2 分層定理 62 6.2.1 空間、時間可構造函數 62 6.2.2 分層定理 63 6.2.3 非確定性時間分層定理 66 6.3 定理A的證明 67 6.4 Ladner定理的證明 69 6.5 復雜性理論常用證明方法總結 70 習題 70 第7章 空間復雜性 72 7.1 PSPACE類 72 7.1.1 Savitch定理 72 7.1.2 PSPACE完全性 74 7.1.3 定理B的證明 76 7.2 L和NL類 77 7.2.1 空間有界的TM 77 7.2.2 L和NL 78 7.2.3 NL完全性 80 7.2.4 NL=coNL 83 習題 85 第8章 隨機化算法與隨機化復雜性類 87 8.1 隨機化算法實例 87 8.1.1 通信復雜性 87 8.1.2 多項式恒等測試 89 8.2 概率圖靈機 91 8.3 隨機化復雜性類 92 8.3.1 單邊錯復雜性類：RP和coRP 92 8.3.2 雙邊錯復雜性類：BPP 94 8.3.3 零邊錯復雜性類：ZPP 96 8.3.4 PP 97 8.4 隨機化復雜性類與其他復雜性類之間的關系 99 8.5 素數問題PRIME 101 8.5.1 PRIME∈NP 102 8.5.2 PRIME∈coRP 104 8.5.3 PRIME∈P 105 習題 106 第9章 密碼學與復雜性理論 107 9.1 單向函數 107 9.2 偽隨機發生器 109 9.3 信息論安全與計算安全 110 第10章 電路復雜性 111 10.1 布爾電路 111 10.2 電路復雜性與P/poly復雜性類 113 10.3 P/poly復雜性類 115 10.4 一致布爾電路 117 10.5 并行計算與Nick復雜性類 118 10.6 BPPP/poly 120 習題 121 第11章 多項式分層 123 11.1 定義與實例 123 11.2 PH的內部結構 124 11.3 交錯式TM與PH的等價定義 125 11.4 PH坍塌 127 習題 129 第12章 交互式證明 130 12.1 IP 131 12.2 公開/保密的隨機性 133 12.3 IP=PSPACE 135 12.4 零知識證明 141 12.5 概率可驗證明(PCP) 143 參考文獻 145