计算复杂性PDF|Epub|txt|kindle电子书版本网盘下载

计算复杂性PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 引言及预备知识1

1.1 引言1

1.1.1 复杂性理论概述2

1.1.2 复杂性理论的特征5

1.1.3 本书内容概要6

1.1.4 写作方法与风格9

1.1.5 标准符号及习惯性用法12

1.2 计算任务及模型13

1.2.1 表达方式14

1.2.2 计算任务15

1.2.3 一致性模型（算法）16

1.2.4 非一致性计算模型（电路及建议）28

1.2.5 复杂性类33

本章注释33

第2章 P、NP和NP-完全性36

2.1 P-vs-NP问题36

2.1.1 搜索版本：求解与检验37

2.1.2 判定版本：证明与验证39

2.1.3 两种表示的等价性42

2.1.4 对NP的两个技术性说明43

2.1.5 NP的传统定义43

2.1.6 对P不同于NP的支持44

2.1.7 哲学思考45

2.2 多项式时间归约46

2.2.1 归约的一般概念46

2.2.2 优化问题到搜索问题的归约48

2.2.3 搜索问题的自归约性50

2.2.4 总结及一般性观点52

2.3 NP-完全性53

2.3.1 定义53

2.3.2 NP-完全问题的存在性54

2.3.3 一些常见的NP-完全问题56

2.3.4 既不属于P也非NP-完全的NP集65

2.3.5 对完全问题的思考67

2.4 三个前沿性问题69

2.4.1 承诺问题69

2.4.2 NP问题的最优搜索算法73

2.4.3 coNP类及其与NP的交集74

本章注释77

习题78

第3章 P与NP的变形86

3.1 非一致的多项式时间86

3.1.1 布尔电路87

3.1.2 接受建议的机器88

3.2 多项式时间层级90

3.2.1 量词的转换91

3.2.2 非确定型预言机93

3.2.3 P/poly-vs-NP问题及PH类95

本章注释97

习题97

第4章 资源越多功能就越强大吗？103

4.1 非一致的复杂性层级103

4.2 时间层级及缝隙104

4.2.1 时间层级104

4.2.2 时间缝隙及加速109

4.3 空间层级和缝隙112

本章注释112

习题113

第5章 空间复杂性116

5.1 预备知识及相关问题116

5.1.1 几个重要的习惯性表达116

5.1.2 有用的最少计算空间117

5.1.3 时间与空间117

5.1.4 电路求值123

5.2 对数空间123

5.2.1 L类123

5.2.2 对数空间归约123

5.2.3 对数空间一致性及更强的概念124

5.2.4 无向连通性125

5.3 非确定的空间复杂性130

5.3.1 两个模型130

5.3.2 NL及有向连通性131

5.3.3 回顾与讨论137

5.4 PSPACE及游戏137

本章注释140

习题140

第6章 随机性与计数149

6.1 概率多项式时间149

6.1.1 基本模型149

6.1.2 双边错误：BPP类152

6.1.3 单边错误：RP和coRP类155

6.1.4 零边错误：ZPP类159

6.1.5 随机的对数空间160

6.2 计数162

6.2.1 精确计数162

6.2.2 近似计数169

6.2.3 对唯一解的搜索173

6.2.4 解的均匀生成176

本章注释182

随机算法183

计数问题184

习题185

第7章 困难性的用途195

7.1 单向函数195

7.1.1 困难实例的生成与单向函数195

7.1.2 弱单向函数的放大198

7.1.3 困难核心谓词201

7.1.4 对困难放大的思考206

7.2 E中的困难问题206

7.2.1 对多项式规模电路的放大208

7.2.2 对指数规模电路的放大219

本章注释225

习题226

第8章 伪随机数发生器235

8.1 通用模式235

8.2 通用的伪随机数发生器236

8.2.1 基本概念237

8.2.2 典型应用237

8.2.3 计算不可区分性240

8.2.4 扩张函数的放大243

8.2.5 构造245

8.2.6 非一致的强伪随机数发生器247

8.2.7 更强的概念及思考249

8.3 对时间复杂性类的去随机化250

8.3.1 正则去随机性发生器250

8.3.2 正则去随机性发生器的构造253

8.3.3 技术上的变化及概念思考256

8.4 空间受限的区分器257

8.4.1 定义258

8.4.2 两种构造260

8.5 特殊用途的伪随机数发生器265

8.5.1 两两独立发生器266

8.5.2 小偏移发生器269

8.5.3 扩张图上的随机漫游272

本章注释273

习题276

第9章 概率证明系统288

9.1 交互式证明系统288

9.1.1 动机和观点288

9.1.2 定义290

9.1.3 交互式证明的功能292

9.1.4 变形及更好的结构：概述297

9.1.5 计算能力受限的证明者：概述299

9.2 零知识证明系统300

9.2.1 定义301

9.2.2 零知识证明的功能303

9.2.3 知识的证明——附加内容308

9.3 概率可检验证明系统309

9.3.1 定义310

9.3.2 概率可检验证明的功能311

9.3.3 PCP与近似325

9.3.4 对PCP自身的更多讨论：概述326

本章注释329

习题331

第10章 对复杂性要求的弱化339

10.1 近似339

10.1.1 搜索或优化340

10.1.2 判定或属性检测344

10.2 平均情况复杂性348

10.2.1 基础理论349

10.2.2 研究分支359

本章注释367

习题368

附录A 复杂性类汇总375

A.1 预备知识375

A.2 基于算法的类376

A.2.1 时间复杂性类376

A.2.2 空间复杂性类378

A3 基于电路的类379

附录B 寻求下限380

B.1 预备知识380

B.2 布尔电路的复杂性381

B.2.1 基本结论和问题382

B.2.2 单调电路383

B.2.3 有界深度电路383

B.2.4 公式规模384

B.3 算术电路384

B.3.1 单变量多项式385

B.3.2 多变量多项式385

B.4 证明的复杂性386

B.4.1 逻辑证明系统388

B.4.2 代数证明系统388

B.4.3 几何证明系统389

附录C 现代密码学基础390

C.1 引言与预备知识390

C.1.1 基本原则390

C.1.2 计算模型392

C.1.3 内容组织393

C.2 计算困难性393

C.2.1 单向函数394

C.2.2 困难核心谓词395

C.3 伪随机性395

C.3.1 计算不可区分性396

C.3.2 伪随机数发生器396

C.3.3 伪随机函数397

C.4 零知识398

C.4.1 仿真范式398

C.4.2 确切定义399

C.4.3 一般性结论及应用400

C.4.4 其他定义及相关概念401

C.5 加密方案403

C.5.1 定义404

C.5.2 构造方法406

C.5.3 超越窃听的安全性407

C.6 签名和消息认证407

C.6.1 定义408

C.6.2 构造方法409

C.7 通用的密码协议411

C.7.1 定义方法及模型411

C.7.2 一些已知结论414

C.7.3 构造方法及两个简单协议415

C.7.4 结语418

附录D 概率论基础及随机性中的前沿问题420

D.1 概率论基础420

D.1.1 符号约定420

D.1.2 3个不等式421

D.2 散列424

D.2.1 定义424

D.2.2 构造425

D.2.3 剩余Hash引理425

D.3 采样428

D.3.1 定义的环境429

D.3.2 已知结论429

D.3.3 碰撞器431

D.4 随机提取器431

D.4.1 定义及各种观点432

D.4.2 构造436

附录E 明确的构造439

E.1 纠错码439

E.1.1 基本概念439

E.1.2 几种流行的码441

E.1.3 两个计算问题444

E.1.4 列表译码的上界445

E.2 扩张图446

E.2.1 定义和性质446

E.2.2 构造451

附录F 一些省略的证明455

F.1 证明PH可归约为＃P455

F.2 证明IP（f）？AM（O（f））？AM（f）460

F.2.1 利用AM-游戏模拟通用的交互式证明460

F.2.2 AM的线性加速465

附录G 一些计算问题470

G.1 图470

G.2 布尔公式472

G.3 有限域、多项式及向量空间473

G.4 矩阵的行列式与常值473

G.5 素数与合数474

参考文献475

后记485