《结构复杂性原理》求取 ⇩

第一章 基本概念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