计算复杂性理论基础

第0章 引言
习题
第1章 一些计算问题
习题
第2章 逻辑概述
2.1 布尔逻辑
2.2 一阶逻辑
2.3 公理和证明
2.4 存在二阶逻辑
第3章 计算模型
3.1 字符串、编码
3.2 算法时间的度量与模型
3.3 图灵机基础
3.4 多带图灵机、时间与空间
3.5 非确定图灵机
3.6 通用图灵机
3.7 递归语言与递归可枚举语言
习题
第4章 不可判定性
4.1 对角化方法与停机问题
4.2 递归可枚举语言的形式表达
习题
第5章 计算复杂类
5.1 复杂类
5.2 分离定理
5.3 可达性方法
习题
第6章 归约和完备性
6.1 归约
6.2 完备性
6.3 逻辑刻画
6.4 NP一关系
6.5 Oracle图灵机
6.6 自归约
习题
第7章 NP-完备问题、coNP与函数计算
7.1 NP-完备问题
7.1.1 可满足问题的一些变形
7.1.2 图论中的NP-完备问题
7.1.3 集合与数
7.2 伪多项式算法和强NP-完备问题
7.3 P与NP
7.4 函数问题
7.5 coNP
习题
第8章 随机化计算
8.1 随机化算法
8.1.1 概率素性检验
8.1.2 符号行列式
8.1.3 随机游动
8.2 概率计算
8.3 RP，coRP，ZPP和PP语言类
8.4 鲁棒性
习题
第9章 电路复杂度和非一致多项式时间类
9.1 电路复杂度
9.2 单调电路（Monotone Circuits）
9.3 非一致多项式时间类（P／Poly）
第10章 几类语言类介绍
10.1 多项式谱系（Dolynomial Hierarchy）
10.1.1 多项式谱系的定义（PH）
10.1.2 交错图灵机与多项式谱系（PH）
10.2 交互证明系统
10.2.1 证明
10.2.2 交互证明系统IP
10.2.3 公共掷币系统和轮数
10.3 概率可验证证明系统
10.3.1 PCP系统
10.3.2 PCP系统与交互证明系统
10.3.3 PCP语言
10.3.4 复杂度度量
10.3.5 PCP系统的相关结论
10.4 计数类
术语中英文对照表
索引
参考文献