第0章 绪论 1
0.1自动机、可计算性与复杂性 1
0.1.1计算复杂性理论 1
0.1.2可计算性理论 2
0.1.3自动机理论 2
0.2数学概念和术语 2
0.2.1集合 2
0.2.2序列和多元组 4
0.2.3函数和关系 4
0.2.4图 6
0.2.5字符串和语言 8
0.2.6布尔逻辑 9
0.2.7数学名词汇总 10
0.3定义、定理和证明 11
0.4证明的类型 13
0.4.1构造性证明 13
0.4.2反证法 14
0.4.3归纳法 15
练习 16
问题 17
习题选解 18
第一部分 自动机与语言 20
第1章 正则语言 20
1.1有穷自动机 20
1.1.1有穷自动机的形式化定义 22
1.1.2有穷自动机举例 23
1.1.3计算的形式化定义 25
1.1.4设计有穷自动机 25
1.1.5正则运算 27
1.2非确定性 29
1.2.1非确定型有穷自动机的形式化定义 32
1.2.2 NFA与DFA的等价性 33
1.2.3在正则运算下的封闭性 36
1.3正则表达式 38
1.3.1正则表达式的形式化定义 38
1.3.2与有穷自动机的等价性 40
1.4非正则语言 46
练习 50
问题 54
习题选解 58
第2章 上下文无关文法 62
2.1上下文无关文法概述 62
2.1.1上下文无关文法的形式化定义 63
2.1.2上下文无关文法举例 64
2.1.3设计上下文无关文法 65
2.1.4歧义性 66
2.1.5乔姆斯基范式 67
2.2下推自动机 68
2.2.1下推自动机的形式化定义 69
2.2.2下推自动机举例 70
2.2.3与上下文无关文法的等价性 72
2.3非上下文无关语言 77
2.4确定型上下文无关语言 79
2.4.1 DCFL的性质 82
2.4.2确定型上下文无关文法 83
2.4.3 DPDA和DCFG的关系 91
2.4.4语法分析和LR（k）文法 94
练习 96
问题 98
习题选解 100
第二部分 可计算性理论 104
第3章 丘奇-图灵论题 104
3.1图灵机 104
3.1.1图灵机的形式化定义 105
3.1.2图灵机的例子 107
3.2图灵机的变形 110
3.2.1多带图灵机 111
3.2.2非确定型图灵机 112
3.2.3枚举器 113
3.2.4与其他模型的等价性 114
3.3算法的定义 114
3.3.1希尔伯特问题 115
3.3.2描述图灵机的术语 116
练习 118
问题 119
习题选解 120
第4章 可判定性 122
4.1可判定语言 122
4.1.1与正则语言相关的可判定性问题 122
4.1.2与上下文无关语言相关的可判定性问题 124
4.2不可判定性 126
4.2.1对角化方法 127
4.2.2不可判定语言 130
4.2.3一个图灵不可识别语言 131
练习 132
问题 133
习题选解 134
第5章 可归约性 136
5.1语言理论中的不可判定问题 136
5.2一个简单的不可判定问题 143
5.3映射可归约性 148
5.3.1可计算函数 148
5.3.2映射可归约性的形式化定义 148
练习 151
问题 151
习题选解 153
第6章 可计算性理论的高级专题 155
6.1递归定理 155
6.1.1自引用 155
6.1.2递归定理的术语 157
6.1.3应用 158
6.2逻辑理论的可判定性 159
6.2.1一个可判定的理论 161
6.2.2一个不可判定的理论 163
6.3图灵可归约性 164
6.4信息的定义 165
6.4.1极小长度的描述 166
6.4.2定义的优化 168
6.4.3不可压缩的串和随机性 168
练习 170
问题 170
习题选解 171
第三部分 复杂性理论 174
第7章 时间复杂性 174
7.1度量复杂性 174
7.1.1大O和小o记法 174
7.1.2分析算法 176
7.1.3模型间的复杂性关系 178
7.2 P类 180
7.2.1多项式时间 180
7.2.2 P中的问题举例 181
7.3 NP类 184
7.3.1 NP中的问题举例 187
7.3.2 P与NP问题 188
7.4 NP完全性 188
7.4.1多项式时间可归约性 189
7.4.2 NP完全性的定义 191
7.4.3库克-列文定理 192
7.5几个NP完全问题 196
7.5.1顶点覆盖问题 196
7.5.2哈密顿路径问题 198
7.5.3子集和问题 201
练习 202
问题 203
习题选解 207
第8章 空间复杂性 208
8.1萨维奇定理 209
8.2 PSPACE类 210
8.3 PSPACE完全性 211
8.3.1 TQBF问题 212
8.3.2博弈的必胜策略 214
8.3.3广义地理学 215
8.4 L类和NL类 219
8.5 N L完全性 220
8.6 NL等于coNL 222
练习 224
问题 224
习题选解 226
第9章 难解性 228
9.1层次定理 228
9.2相对化 236
9.3电路复杂性 238
练习 244
问题 245
习题选解 245
第10章 复杂性理论高级专题 247
10.1近似算法 247
10.2概率算法 248
10.2.1 BPP类 249
10.2.2素数性 250
10.2.3只读一次的分支程序 254
10.3交错式 257
10.3.1交错式时间与交错式空间 257
10.3.2多项式时间层次 260
10.4交互式证明系统 260
10.4.1图的非同构 261
10.4.2模型的定义 261
10.4.3 IP= PSPACE 263
10.5并行计算 270
10.5.1一致布尔电路 270
10.5.2 NC类 272
10.5.3 P完全性 273
10.6密码学 273
10.6.1密钥 274
10.6.2公钥密码系统 275
10.6.3单向函数 275
10.6.4天窗函数 277
练习 277
问题 278
习题选解 278
参考文献 280
索引 284