- 作 者：吕义忠，孙慧澄编著
- 出 版 社：南京：南京大学出版社
- 出版年份：1995
- ISBN：730502760X
- 注意：在使用云解压之前，请认真核对实际PDF页数与内容!
在线云解压
价格(点数)
购买连接
说明
转为PDF格式
8
（在线云解压服务）
云解压服务说明
1、本站所有的云解压默认都是转为PDF格式，该格式图书只能阅读和打印，不能再次编辑。
云解压下载及付费说明
1、所有的电子图书云解压均转换为PDF格式，支持电脑、手机、平板等各类电子设备阅读；可以任意拷贝文件到不同的阅读设备里进行阅读。
2、云解压在提交订单后一般半小时内处理完成,最晚48小时内处理完成。(非工作日购买会延迟)
第一章 基本概念 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