结构复杂性原理PDF电子书下载

第一章 基本概念 1

1.1 概述 1

1.2 计算模型 2

1.3 集合与类 7

1.4 布尔公式 8

第二章 资源受限的计算 10

2.1 图灵机的计算时间和计算空间 10

2.2 空间压缩定理和时间加速定理 11

2.3 空间和时间的可构造性 13

2.4 资源受限的复杂类 17

第三章 基本复杂类 23

3.1 基本复杂类的定义和性质 23

3.2 多项式可计算函数 28

3.3 多一化归与NP完全集 32

3.4 NP完全问题的多项式同构 38

3.5 稀疏的NP完全集 46

3.6 PSPACE完全性 53

第四章 非一致复杂性 56

4.1 超前函数 56

4.2 布尔线路 57

4.3 布尔线路与图灵机的关系 60

4.4 多项式超前函数 64

4.5 单行函数 72

第五章 概率复杂性 76

5.1 合数算法 76

5.2 概率图灵机 77

5.3 概率复杂类 79

5.4 有界出错概率复杂类 83

5.5 BPP的非一致性质 87

5.6 零出错概率 89

第六章 多项式时间分层 92

6.1 多项式分层与相对化 92

6.2 多项式时间分层的相对化定义 95

6.3 多项式分层的基本性质 95

6.4 交替有界量词及其分层性质 97

6.5 分层的概率复杂性 103

第七章 禁集与核 108

7.1 双禁集、复杂核与分裂 108

7.2 双禁集与多一化归 110

7.3 复杂核与多一化归 114

7.4 真核与分层 118

第八章 相对化理论 122

8.1 基本的相对化结果 123

8.2 保持P（A）≠NP（A）的相对化结果 128

8.3 概率复杂类的相对化结果 132

第九章 相对化原理 135

9.1 P-PSPACE问题的正相对化结果 136

9.2 NP-PSPACE问题的正相对化结果 139

9.3 P-NP问题的正相对化结果 142

9.4 P-NP问题的相对化原理 145

第十章 高分层与低分层 149

10.1 引言 149

10.2 定义与性质 149

10.3 高类、低类与多项式分层 153

10.4 低类的一些性质 158

10.5 分类Oracle的相对化结果 164

10.6 超越NP的低类 167

第十一章 哥氏复杂性 170

11.1 引言 170

11.2 无界哥氏复杂性 170

11.3 哥氏复杂性的例子 171

11.4 资源受限的哥氏复杂性 172

11.5 单元集、可印性和秩 175

11.6 特征函数的哥氏复杂性 183

索引 185