第0章 记号约定 1
0.1 对象的字符串表示 1
O.2 判定问题／语言 2
0.3 大O记号 2
习题 3
第一部分 基本复杂性类 6
第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 类P 18
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 类NP 29
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.1 1的证明 35
2.3.5 将SAT归约到3SAT 38
2.3.6 深入理解库克－勒维定理 38
2.4 归约网络 39
2.5 判定与搜索 42
2.6 coNP、EXP和NEXP 43
2.6.1 coNP 43
2.6.2 EXP和NEXP 44
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=coNL 71
本章学习内容 72
本章注记和历史 73
习题 73
第5章 多项式分层和交错 75
5.1 类∑p2 75
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/poly 83
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和NP 88
6.5 线路下界 89
6.6 非一致分层定理 90
6.7 线路复杂性类的精细分层 91
6.7.1 类NC和类AC 92
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、ZPP 103
7.4 定义的健壮性 103
7.4.1 准确度常数的作用：错率归约 104
7.4.2 期望运行时间与最坏运行时间 105
7.4.3 使用比均匀硬币投掷更具一般性的随机选择 106
7.5 BPP同其他复杂性类之间的关系 106
7.5.1 BPP？P/poly 107
7.5.2 BPP？PH 107
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 公用随机源和类AM 118
8.2.1 私有随机源的模拟 119
8.2.2 集合下界协议 120
8.2.3 定理8.1 2的证明概要 123
8.2.4 GI能是NP－完全的吗 123
8.3 IP=PSPACE 124
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 量子计算的定义和BQP 168
10.3.1 线性代数预备知识 168
10.3.2 量子寄存器及其状态向量 168
10.3.3 量子操作 169
10.3.4 量子操作实例 169
10.3.5 量子计算与BQP 171
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？PCP（poly（n），1）：由沃尔什－哈达玛编码得到的PCP 202
11.5.1 线性测试与沃尔什－哈达玛编码 202
11.5.2 定理11.19的证明 203
本章学习内容 206
本章注记和历史 206
习题 207
第二部分 具体计算模型的下界 210
第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 带“计数器”的线路：ACC 236
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
第三部分 高级专题 278
第17章 计数复杂性 278
17.1 计数问题举例 278
17.1.1 计数问题与概率估计 279
17.1.2 计数可能难于判定 279
17.2 复杂性类＃P 280
17.2.1 复杂性类PP：类似于＃P的判定问题 281
17.3 ＃P完全性 281
17.3.1 积和式和瓦利安特定理 282
17.3.2 ＃P问题的近似解 286
17.4 户田定理：PH？P＃SAT 287
17.4.1 过渡：具有唯一解的布尔满足性问题 288
17.4.2 ？的性质和对NP、coNP证明引理17.17 289
17.4.3 引理17.1 7的证明：一般情形 290
17.4.4 第二步：转换为确定型归约 291
17.5 待决问题 292
本章学习内容 293
本章注记和历史 293
习题 293
第18章 平均复杂性：勒维定理 295
18.1 分布问题与distP 296
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=P 323
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.1 6的证明 396
22.8 SET-COVER的近似难度 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