绪论 计算复杂性理论简介
0.1 计算复杂性理论的首要问题
0.2 计算复杂性理论与算法理论的区别
0.3 计算理论及其组成
0.4 计算复杂性理论与密码学的关系
第1章 计算模型——Turing机
1.1 常用术语和记号
1.2 Turing机
1.2.1 Turing机的基本模型
1.2.2 TM的形式化定义
1.2.3 TM的格局
1.2.4 TM举例
1.2.5 描述TM的不同方式
1.3 TM的稳健性
1.4 ChurchTuring命题
1.5 非确定性TM
1.6 通用TM
习题
第2章 计算任务与复杂性
2.1 关心的计算任务：判定语言
2.2 复杂性的度量
2.2.1 大O小o记号
2.2.2 时间/空间复杂性的定义
2.2.3 两个事实
2.2.4 采用大O记号的合理性——带压缩定理和线性加速定理
2.2.5 带数目的减少对时间复杂度和空间复杂度的影响
2.2.6 DTM与NDTM的时间复杂性关系
2.3 复杂性类
2.3.1 复杂性类的概念
2.3.2 TIME和SPACE之间的平凡(trivial)关系
习题
第3章 P与NP
3.1 P 类
3.1.1 P的定义
3.1.2 P的重要性
3.1.3 P中的问题
3.2 NP 类
3.2.1 NP的定义
3.2.2 NP中的问题
3.2.3 世纪难题 P =? NP
3.2.4 NP的等价定义
3.3 coNP与coNP=? NP
习题
第4章 归约与NP完全性
4.1 历史背景
4.2 归约
4.2.1 Cook归约
4.2.2 Karp归约
4.2.3 Levin归约
4.3 NP完全性
4.4 CookLevin定理
4.5 更多NP完全问题
4.6 其他NPC问题
习题
第5章 关于P和NP的更多知识
5.1 查找与判定：NPC问题的自归约特性
5.1.1 SAT的自归约特性
5.1.2 CLIQUE的自归约特性
5.1.3 NPC问题都满足自归约特性
5.2 NPI语言
5.3 P vs NP
5.3.1 哈密尔顿回路vs 欧拉回路
5.3.2 三色vs四色
5.3.3 3SAT vs 2SAT
5.4 Oracle TM——相对化
习题
第6章 对角化方法
6.1 对角化方法与不可判定问题的存在性
6.1.1 可数集与对角化方法
6.1.2 不可判定问题的存在性
6.1.3 停机问题不可判定
6.2 分层定理
6.2.1 空间、时间可构造函数
6.2.2 分层定理
6.2.3 非确定性时间分层定理
6.3 定理A的证明
6.4 Ladner定理的证明
6.5 复杂性理论常用证明方法总结
习题
第7章 空间复杂性
7.1 PSPACE类
7.1.1 Savitch定理
7.1.2 PSPACE完全性
7.1.3 定理B的证明
7.2 L和NL类
7.2.1 空间有界的TM
7.2.2 L和NL
7.2.3 NL完全性
7.2.4 NL=coNL
习题
第8章 随机化算法与随机化复杂性类
8.1 随机化算法实例
8.1.1 通信复杂性
8.1.2 多项式恒等测试
8.2 概率图灵机
8.3 随机化复杂性类
8.3.1 单边错复杂性类：RP和coRP
8.3.2 双边错复杂性类：BPP
8.3.3 零边错复杂性类：ZPP
8.3.4 PP
8.4 随机化复杂性类与其他复杂性类之间的关系
8.5 素数问题PRIME
8.5.1 PRIME∈NP
8.5.2 PRIME∈coRP
8.5.3 PRIME∈P
习题
第9章 密码学与复杂性理论
9.1 单向函数
9.2 伪随机发生器
9.3 信息论安全与计算安全
第10章 电路复杂性
10.1 布尔电路
10.2 电路复杂性与P/poly复杂性类
10.3 P/poly复杂性类
10.4 一致布尔电路
10.5 并行计算与Nick复杂性类
10.6 BPPP/poly
习题
第11章 多项式分层
11.1 定义与实例
11.2 PH的内部结构
11.3 交错式TM与PH的等价定义
11.4 PH坍塌
习题
第12章 交互式证明
12.1 IP
12.2 公开/保密的随机性
12.3 IP=PSPACE
12.4 零知识证明
12.5 概率可验证明（PCP）
参考文献
展开
