计算复杂性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可归约为＃P 455

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