第1章 引言及预备知识

1.1 引言

1.1.1 复杂性理论概述

1.1.2 复杂性理论的特征

1.1.3 本书内容概要

1.1.4 写作方法与风格

1.1.5 标准符号及习惯性用法

1.2 计算任务及模型

1.2.1 表达方式

1.2.2 计算任务

1.2.3 一致性模型（算法）

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

1.2.5 复杂性类

本章注释

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

2.1 P-vs-NP问题

2.1.1 搜索版本：求解与检验

2.1.2 判定版本：证明与验证

2.1.3 两种表示的等价性

2.1.4 对NP的两个技术性说明

2.1.5 NP的传统定义

2.1.6 对P不同于NP的支持

2.1.7 哲学思考

2.2 多项式时间归约

2.2.1 归约的一般概念

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

2.2.3 搜索问题的自归约性

2.2.4 总结及一般性观点

2.3 NP-完全性

2.3.1 定义

2.3.2 NP-完全问题的存在性

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

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

2.3.5 对完全问题的思考

2.4 三个前沿性问题

2.4.1 承诺问题

2.4.2 NP问题的最优搜索算法

2.4.3 coNP类及其与NP的交集

本章注释

习题

第3章 P与NP的变形

3.1 非一致的多项式时间

3.1.1 布尔电路

3.1.2 接受建议的机器

3.2 多项式时间层级

3.2.1 量词的转换

3.2.2 非确定型预言机

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

本章注释

习题

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

4.1 非一致的复杂性层级

4.2 时间层级及缝隙

4.2.1 时间层级

4.2.2 时间缝隙及加速

4.3 空间层级和缝隙

本章注释

习题

第5章 空间复杂性

5.1 预备知识及相关问题

5.1.1 几个重要的习惯性表达

5.1.2 有用的最少计算空间

5.1.3 时间与空间

5.1.4 电路求值

5.2 对数空间

5.2.1 L类

5.2.2 对数空间归约

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

5.2.4 无向连通性

5.3 非确定的空间复杂性

5.3.1 两个模型

5.3.2 NL及有向连通性

5.3.3 回顾与讨论

5.4 PSPACE及游戏

本章注释

习题

第6章 随机性与计数

6.1 概率多项式时间

6.1.1 基本模型

6.1.2 双边错误：BPP类

6.1.3 单边错误：RP和coRP类

6.1.4 零边错误：ZPP类

6.1.5 随机的对数空间

6.2 计数

6.2.1 精确计数

6.2.2 近似计数

6.2.3 对唯一解的搜索

6.2.4 解的均匀生成

本章注释

随机算法

计数问题

习题

第7章 困难性的用途

7.1 单向函数

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

7.1.2 弱单向函数的放大

7.1.3 困难核心谓词

7.1.4 对困难放大的思考

7.2 E中的困难问题

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

7.2.2 对指数规模电路的放大

本章注释

习题

第8章 伪随机数发生器

8.1 通用模式

8.2 通用的伪随机数发生器

8.2.1 基本概念

8.2.2 典型应用

8.2.3 计算不可区分性

8.2.4 扩张函数的放大

8.2.5 构造

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

8.2.7 更强的概念及思考

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

8.3.1 正则去随机性发生器

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

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

8.4 空间受限的区分器

8.4.1 定义

8.4.2 两种构造

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

8.5.1 两两独立发生器

8.5.2 小偏移发生器

8.5.3 扩张图上的随机漫游

本章注释

习题

第9章 概率证明系统

9.1 交互式证明系统

9.1.1 动机和观点

9.1.2 定义

9.1.3 交互式证明的功能

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

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

9.2 零知识证明系统

9.2.1 定义

9.2.2 零知识证明的功能

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

9.3 概率可检验证明系统

9.3.1 定义

9.3.2 概率可检验证明的功能

9.3.3 PCP与近似

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

本章注释

习题

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

10.1 近似

10.1.1 搜索或优化

10.1.2 判定或属性检测

10.2 平均情况复杂性

10.2.1 基础理论

10.2.2 研究分支

本章注释

习题

附录A 复杂性类汇总

A.1 预备知识

A.2 基于算法的类

A.2.1 时间复杂性类

A.2.2 空间复杂性类

A3 基于电路的类

附录B 寻求下限

B.1 预备知识

B.2 布尔电路的复杂性

B.2.1 基本结论和问题

B.2.2 单调电路

B.2.3 有界深度电路

B.2.4 公式规模

B.3 算术电路

B.3.1 单变量多项式

B.3.2 多变量多项式

B.4 证明的复杂性

B.4.1 逻辑证明系统

B.4.2 代数证明系统

B.4.3 几何证明系统

附录C 现代密码学基础

C.1 引言与预备知识

C.1.1 基本原则

C.1.2 计算模型

C.1.3 内容组织

C.2 计算困难性

C.2.1 单向函数

C.2.2 困难核心谓词

C.3 伪随机性

C.3.1 计算不可区分性

C.3.2 伪随机数发生器

C.3.3 伪随机函数

C.4 零知识

C.4.1 仿真范式

C.4.2 确切定义

C.4.3 一般性结论及应用

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

C.5 加密方案

C.5.1 定义

C.5.2 构造方法

C.5.3 超越窃听的安全性

C.6 签名和消息认证

C.6.1 定义

C.6.2 构造方法

C.7 通用的密码协议

C.7.1 定义方法及模型

C.7.2 一些已知结论

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

C.7.4 结语

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

D.1 概率论基础

D.1.1 符号约定

D.1.2 3个不等式

D.2 散列

D.2.1 定义

D.2.2 构造

D.2.3 剩余Hash引理

D.3 采样

D.3.1 定义的环境

D.3.2 已知结论

D.3.3 碰撞器

D.4 随机提取器

D.4.1 定义及各种观点

D.4.2 构造

附录E 明确的构造

E.1 纠错码

E.1.1 基本概念

E.1.2 几种流行的码

E.1.3 两个计算问题

E.1.4 列表译码的上界

E.2 扩张图

E.2.1 定义和性质

E.2.2 构造

附录F 一些省略的证明

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

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

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

F.2.2 AM的线性加速

附录G 一些计算问题

G.1 图

G.2 布尔公式

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

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

G.5 素数与合数

参考文献

后记