第十三章：Lower bound 与证明障碍

upper bound 只需给出一个算法；lower bound 要排除模型中的全部算法。模型越接近一般计算，候选算法的结构越少，证明越困难。

Lower bound 的量词

一个时间 lower bound 形如

$$\forall A\in\mathcal M,\ \exists x,\ \operatorname{cost}_A(x)\ge g(|x|),$$

其中 $\mathcal M$ 是明确的模型集合。证明必须依赖所有 $A\in\mathcal M$ 都具有的性质。

常见方法包括：

• information counting：有限 transcript 无法区分全部输入；
• adversary：回答查询时维持多个候选；
• combinatorial structure：rectangle、sunflower、random restriction；
• algebraic method：rank、polynomial degree、spectral bound；
• diagonalization：构造与枚举机器逐一不同的 language；
• reduction：把已知 lower bound 或复杂度假设传递给目标。

Counting argument

大小 $s$ 的 Boolean circuit 数量至多约

$$2^{O(s\log s)}.$$

而 $n$-bit Boolean function 总数为

$$2^{2^n}.$$

因此几乎所有 Boolean function 都需要大小 $\Omega(2^n/n)$ 的 circuit。

该结论很强，却没有给出一个易描述、可显式计算的困难函数。复杂度理论需要对 SAT、Clique 等 explicit function 证明 lower bound，而不是证明随机真值表困难。

Explicitness

“显式”可有不同强度：

• truth table 可以在指数时间生成；
• 函数属于 $\mathsf{EXP}$；
• 函数属于 $\mathsf{NP}$；
• 函数属于 $\mathsf P$。

目标越显式，circuit lower bound 越困难。证明某个 NP language 不具有 polynomial circuit 将推出

$$\mathsf{NP}\nsubseteq\mathsf{P/poly},$$

并进一步得到 $\mathsf P\ne\mathsf{NP}$。

已知 separation 的来源

无条件 separation 主要来自能够控制模型的场景：

• time/space hierarchy：带资源时钟的对角化；
• $\mathsf{AC^0}$：random restriction 与 switching lemma；
• monotone circuit：单调组合结构；
• communication/query：信息或输入访问限制；
• proof system：特定推理规则的结构限制。

这些结果说明 lower-bound technique 可以成功，但每种方法都依赖目标模型的受限性质。

Relativization

oracle Turing machine 可以单位时间查询某 language $A$。定义相对化类 $\mathsf P^A,\mathsf{NP}^A$。

Baker–Gill–Solovay 证明存在 oracle $A,B$ 使

$$\mathsf P^A=\mathsf{NP}^A, \qquad \mathsf P^B\ne\mathsf{NP}^B.$$

因此，任何对所有 oracle 都保持的证明方法不能解决 $\mathsf P$ vs $\mathsf{NP}$。普通 diagonalization、simulation 和许多早期方法会 relativize。

oracle 结果不表示真实世界同时满足等式与不等式，也不证明目标不可解决；它是对证明方法适用范围的 barrier。

Natural proofs

Razborov–Rudich 将一类 circuit lower-bound 方法抽象为 Boolean function 的性质，要求：

• constructivity：可较高效判断真值表是否具有该性质；
• largeness：足够大比例函数具有该性质；
• usefulness：具有该性质的函数不可能由小 circuit 计算。

在强伪随机函数存在的假设下，不存在同时满足这些条件、足以证明一般 circuit lower bound 的 natural property。否则该性质可区分伪随机函数与随机函数。

natural proofs barrier 解释了许多组合 lower bound 方法难以扩展到一般 circuit；它不排除非 constructive、non-large 或使用其他结构的方法。

Algebrization

某些非相对化结果使用 arithmetization，把 Boolean 计算扩展到低次多项式。algebrization barrier 进一步允许 oracle 的代数扩展，并展示仍有相反的 oracle 世界。

因此，仅加入标准 arithmetization 仍不足以解决若干主要 separation。与 relativization 一样，该结论限制方法类别，而非限制定理真值。

Conditional lower bound

当无条件 lower bound 不可得时，可以明确采用复杂度假设：

$$\text{SETH}\Rightarrow \text{目标问题不存在 }O(n^{2-\varepsilon})\text{ 算法}.$$

条件 lower bound 的有效性取决于：

1. 基础假设的精确定义；
2. reduction 对参数和 exponent 的保持；
3. 随机化、近似和预处理是否被允许；
4. 结论针对 worst case 还是 average case。

条件结论不能省略假设表述为无条件 lower bound，但它可以解释多个问题为何具有共同算法屏障。

Separation 与 collapse evidence

未能直接证明 separation 时，常研究某个假设会导致哪些后果：

• NP-complete 问题属于 P $\Rightarrow \mathsf P=\mathsf{NP}$；
• NP-complete 问题属于 coNP $\Rightarrow \mathsf{NP}=\mathsf{coNP}$；
• $\mathsf{NP}\subseteq\mathsf{P/poly}\Rightarrow\mathsf{PH}$ collapse；
• polynomially bounded proof system $\Rightarrow\mathsf{NP}=\mathsf{coNP}$。

这些 implication 构成结构证据，但都不是矛盾。复杂度理论中“认为不可能”通常来自大量此类一致证据，而非单个定理。

分析新问题的流程

面对新的计算问题，可以按以下顺序建立理论结论：

1. 对象：是 language、function、relation、promise 还是 distributional problem？
2. 编码：输入长度、数值位数和输出长度如何定义？
3. 模型：使用 RAM、circuit、protocol、query 还是 quantum circuit？
4. 资源：限制时间、空间、depth、通信、查询、随机位还是证明长度？
5. upper bound：已有算法实现在哪个模型中，错误和近似保证是什么？
6. reduction：哪些已知问题可以归约到它，参数损失是多少？
7. lower bound：目标是无条件受限模型下界，还是基于假设的条件下界？
8. barrier：现有方法是否 relativize、naturalize 或 algebrize？

该流程使“问题很难”分解为可验证陈述。计算理论的主要作用不是为困难程度贴标签，而是明确结论依赖的模型、资源和证明范围。

综合自测

1. counting argument 为什么只能说明大多数函数困难，而不能直接处理 SAT？
2. oracle 给出的相反世界限制了哪类证明方法？
3. natural proofs 的 constructivity、largeness、usefulness 分别表示什么？
4. conditional lower bound 中 reduction 为什么必须保持 exponent？
5. “若某算法存在则 PH collapse”为什么是证据而不是矛盾？

上一章：量子计算 · 返回课程首页