第一部分 算法 2
第1章 问题与算法 2
1.1 图的可达性问题 2
1.2 最大流问题 4
1.3 旅行商问题 7
1.4 注解、参考文献和问题 7
第2章 图灵机 11
2.1 图灵机概述 11
2.2 视为算法的图灵机 14
2.3 多带图灵机 15
2.4 线性加速 18
2.5 空间界 20
2.6 随机存取机 21
2.7 非确定性机 27
2.8 注解、参考文献和问题 30
第3章 不可判定性 34
3.1 通用图灵机 34
3.2 停机问题 35
3.3 更多不可判定性问题 36
3.4 注解、参考文献和问题 39
第二部分 逻辑学 42
第4章 布尔逻辑 42
4.1 布尔表达式 42
4.2 可满足性与永真性 44
4.3 布尔函数与电路 46
4.4 注解、参考文献和问题 48
第5章 一阶逻辑 51
5.1 一阶逻辑的语法 51
5.2 模型 52
5.3 永真的表达式 56
5.4 公理和证明 60
5.5 完备性定理 64
5.6 完备性定理的推论 67
5.7 二阶逻辑 69
5.8 注解、参考文献和问题 72
第6章 逻辑中的不可判定性 75
6.1 数论公理 75
6.2 作为一个数论概念的计算 77
6.3 不可判定性与不完备性 80
6.4 注解、参考文献和问题 82
第三部分 P和NP 86
第7章 复杂性类之间的关系 86
7.1 复杂性类 86
7.2 谱系定理 88
7.3 可达性方法 91
7.4 注解、参考文献和问题 95
第8章 归约和完备性 99
8.1 归约 99
8.2 完全性 103
8.3 逻辑特征 107
8.4 注解、参考文献和问题 109
第9章 NP完全问题 113
9.1 NP中的问题 113
9.2 可满足性问题的不同版本 114
9.3 图论问题 118
9.4 集合和数字 125
9.5 注解、参考文献和问题 129
第10章 coNP和函数问题 138
10.1 NP和coNP 138
10.2 素性 140
10.3 函数问题 144
10.4 注解、参考文献和问题 148
第11章 随机计算 152
11.1 随机算法 152
11.2 随机复杂性类 160
11.3 随机源 164
11.4 电路复杂性 169
11.5 注解、参考文献和问题 172
第12章 密码学 177
12.1 单向函数 177
12.2 协议 182
12.3 注解、参考文献和问题 186
第13章 可近似性 190
13.1 近似算法 190
13.2 近似和复杂性 197
13.3 不可近似性 204
13.4 注解、参考文献和问题 206
第14章 关于P和NP 211
14.1 NP的地图 211
14.2 同构和稠密性 213
14.3 谕示 217
14.4 单调电路 221
14.5 注解、参考文献和问题 225
第四部分 P内部的计算复杂性类 230
第15章 并行计算 230
15.1 并行算法 230
15.2 计算的并行模型 237
15.3 NC类 241
15.4 RNC算法 244
15.5 注解、参考文献和问题 247
第16章 对数空间 254
16.1 L？NL问题 254
16.2 交错 256
16.3 无向图的可达性 258
16.4 注解、参考文献和问题 260
第五部分 NP之外的计算复杂性类 264
第17章 多项式谱系 264
17.1 优化问题 264
17.2 多项式谱系 273
17.3 注解、参考文献和问题 278
第18章 有关计数的计算 282
18.1 积和式 282
18.2 ？P类 287
18.3 注解、参考文献和问题 289
第19章 多项式空间 291
19.1 交错和博弈 291
19.2 对抗自然的博弈和交互协议 299
19.3 更多的PSPACE完全问题 307
19.4 注解、参考文献和问题 311
第20章 未来的展望 313
20.1 指数时间复杂性类 313
20.2 注解、参考文献和问题 318
索引 324