《计算复杂性》阿罗拉 巴拉克 | PDF下载|ePub下载

出版者的话
译者序
译者简介
前言
致谢
引言
第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.2P的哲学意义19
1.6.3P的争议和解决争议的一些努力20
1.6.4埃德蒙兹的引言21
1.7定理1.9的证明：O（TlogT）时间的通用模拟21
本章学习内容24
本章注记和历史24
习题26
第2章NP和NP完全性29
2.1类NP29
2.1.1P和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.6coNP、EXP和NEXP43
2.6.1coNP43
2.6.2EXP和NEXP44
2.7深入理解P、NP及其他复杂性类45
2.7.1NP的哲学意义45
2.7.2NP与数学证明45
2.7.3如果P=NP会怎样45
2.7.4如果NP=coNP会怎样46
2.7.5NP和NP完全之间存在其他复杂性类吗47
2.7.6NP难的处理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.2PSPACE完全性64
4.2.1塞维奇定理67
4.2.2PSPACE的本质：最佳博弈策略67
4.3NL完全性68
4.3.1基于证明的NL定义：仅能读一次的证明70
4.3.2NL=coNL71
本章学习内容72
本章注记和历史73
习题73
第5章多项式分层和交错75
5.1类Σp275
5.2多项式分层76
5.2.1多项式分层的性质76
5.2.2PH各层的完全问题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.1P／poly和P之间的关系85
6.1.2线路的可满足性和库克勒维定理的另一种证明86
6.2一致线路87
6.2.1对数空间一致线路族87
6.3纳言图灵机88
6.4P／poly和NP88
6.5线路下界89
6.6非一致分层定理90
6.7线路复杂性类的精细分层91
6.7.1类NC和类AC92
6.7.2P完全性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.5BPP同其他复杂性类之间的关系106
7.5.1BPPP／poly107
7.5.2BPPPH107
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.4GI能是NP完全的吗123
8.3IP=PSPACE124
8.3.1算术化125
8.3.2#SATD的交互式协议125
8.3.3TQBF的协议：定理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.1EPR悖论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.1ZM上的傅里叶变换179
10.6.2ZM上的量子傅里叶变换180
10.6.3肖尔的阶发现算法181
10.6.4因数分解归约为阶发现184
10.6.5实数的有理数近似185
10.7BQP和经典复杂性类186
10.7.1量子计算中类似于NP和AM的复杂性类187
本章学习内容187
本章注记和历史188
习题190
第11章PCP定理和近似难度简介192
11.1动机：近似求解NP难的优化问题193
11.2用两种观点理解PCP定理194
11.2.1PCP定理与局部可验证明194
11.2.2PCP定理与近似难度197
11.3两种观点的等价性197
11.3.1定理11.5与定理11.9的等价性198
11.3.2重新审视PCP的两种理解199
11.4顶点覆盖问题和独立集问题的近似难度200
11.5NPPCP（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.1AC0和哈斯塔德开关引理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.2ACCVsP的研究现状243
14.4.3具有对数深度的线性线路244
14.4.4线路图244
14.5通信复杂性方法245
14.5.1与ACCO线路之间的联系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P#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.3distNP及其完全问题298
18.3.1distNP的一个完全问题300
18.3.2P可抽样的分布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.2PCP定理的证明379
22.2.1PCP定理的证明思路379
22.2.2迪纳尔鸿沟放大：引理22.5的证明380
22.2.3扩张图、随机游走和INDSET的近似难度381
22.2.4迪纳尔鸿沟放大382
22.2.5字母表削减：引理22.6的证明387
22.32CSPW的难度：鸿沟和字母表大小之间的平衡389
22.3.1莱斯的证明思想：并行重复389
22.4哈斯塔德3位PCP定理和MAX3SAT的难度390
22.4.1MAX3SAT的近似难度390
22.5工具：傅里叶变换391
22.5.1GF（2）n上的傅里叶变换391
22.5.2从较高层面看傅里叶变换和PCP之间的联系393
22.5.3GF（2）上线性测试的分析393
22.6坐标函数、长编码及其测试395
22.7定理22.16的证明396
22.8SETCOVER的近似难度400
22.9其他PCP定理概述402
22.9.1具有亚常数可靠性参数的PCP定理402
22.9.2平摊的查验复杂度402
22.9.32位测试和高效傅里叶分析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
· · · · · ·