图书介绍
结构复杂性原理pdf电子书版本下载
- 吕义忠，孙慧澄编著 著
- 出版社： 南京：南京大学出版社
- ISBN：730502760X
- 出版时间：1995
- 标注页数：189页
- 文件大小：27MB
- 文件页数：197页
- 主题词：
PDF下载
下载说明
结构复杂性原理PDF格式电子书版下载
下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如 BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！
（文件页数 要大于 标注页数，上中下等多册电子书除外）
注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具
图书目录
第一章 基本概念 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