复杂度类全景

P 与 NP 之外，复杂度类的全景包括空间类（PSPACE）、时间类（EXPTIME）、补类（co-NP）、多项式层级、随机类（BPP）与量子类（BQP）。本章给出各类的包含关系图与已知/未知的分离（→ P、NP 与归约）。

包含关系图

已知包含（实线）与公认猜想（虚线）：

L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXPTIME

P \xrightarrow{\text{?}} NP, \qquad NP \xrightarrow{?} PSPACE, \qquad P \xrightarrow{?} BPP \xrightarrow{?} P

严格分离已知的有： $P \subsetneq EXPTIME$ （时间层级定理）、 $L \subsetneq PSPACE$ （空间层级定理）；其余的分离（如 P vs NP）全部开放。

PSPACE：多项式空间可解——时间可复用，空间不可复用，所以 PSPACE 比 NP 更"大"：

PSPACE 包含 NP，但是否相等未知（NP ⊆ PSPACE 因为穷举证书只需多项式空间）；
PSPACE 的代表问题：博弈——广义棋类（围棋、国际象棋的推广）的"必胜策略"是 PSPACE 完全的：穷举博弈树只需递归栈（多项式空间，指数时间）；
QBF（量词化布尔公式可满足性）是 PSPACE 完全的标准问题。

EXPTIME：指数时间可解——比 PSPACE 更大（PSPACE ⊆ EXPTIME，严格性开放但公认）；广义国际象棋的必胜策略是 EXPTIME 完全（比 PSPACE 完全的围棋更难）；
co-NP：NP 问题的补类——"不存在满足的赋值"（TAUTOLOGY，恒真判定）是 co-NP 完全的。**NP = co-NP 吗？**开放，与 P vs NP 同层未知；
多项式层级（PH）：NP 与 co-NP 的交替扩展（ $\Sigma_k, \Pi_k$ ）——"存在/任意"交替 $k$ 次的公式层级；若 P = NP 则 PH 坍缩——这是 P ≠ NP 的证据形态之一。

BPP：随机算法多项式时间、错误概率 < 1/3 的类——"抛硬币的算法"：

随机化在实践中强大（素性测试的 Miller-Rabin、随机化数据结构与算法）；
BPP 被认为等于 P（去随机化）：伪随机数发生器能把随机位换成伪随机位——这个猜想有强证据（电路复杂度的下界结果支撑），但未证；
素性测试的注脚：AKS 算法（2002）证明素性测试在 P——Miller-Rabin 的随机版被确定性版追赶上了，这是"随机化被去随机化"的罕见实例。

BQP：量子图灵机多项式时间的类——量子叠加与干涉的计算能力：

已知： $BPP \subseteq BQP \subseteq PSPACE$ ；BQP 与 NP 的关系未知（量子是否能解 NP 完全问题是开放问题，多数人认为不能）；
Shor 算法（1994）把因数分解放进 BQP：多项式时间分解大整数——威胁 RSA（其安全性基于因数分解的困难性，→ 公钥密码与密钥交换）；
Grover 算法：无序搜索平方加速（ $O(\sqrt{n})$ ）——只多项式加速，不改变复杂度类；
量子计算的能力来自干涉（错误振幅相消），不是"并行尝试所有答案"——叠加不等于指数并行读取。

层级定理是复杂度理论的"确定性"成果：更多资源严格解决更多问题——但 P vs NP 这类"同层比较"八十年无进展（相对化障碍、自然证明障碍是已知的方法论限制）。

已知包含链： $P \subseteq NP \subseteq PSPACE \subseteq EXPTIME$ ；严格分离只证到 $P \subsetneq EXPTIME$
PSPACE 包含 NP，但是否相等未知；博弈问题是 PSPACE 完全（空间可复用）
BPP 被认为等于 P（去随机化）；AKS 证明素性测试在 P 是实例
Shor 算法把因数分解放进 BQP，威胁 RSA；量子能力来自干涉不是并行读取
多项式层级（PH）：P = NP 则坍缩；多数分离问题仍然开放