自然证明障碍

一个大性质会接受不可忽略比例的真正随机函数；一个有用性质会拒绝所有小电路函数，其中包括由短密钥生成的 PRF 实例；一个构造性判定器又能在读完真值表后有效区分两者。把三项合起来，性质测试器就成了攻击 PRF 的区分器：随机真值表以可见概率被接受，伪随机真值表因有小电路而被拒绝。这与强 PRF 安全性冲突。

障碍揭示的不是某个证明步骤错误，而是许多成功下界共享的一种“随机函数通常具有、且可从真值表有效识别”的结构。弱电路类未必能实现足够强的 PRF，所以同一模板仍可证明 AC⁰ 等下界；当目标升级到能够容纳密码学伪随机性的类，性质越普遍、越可算法识别，越可能反过来成为区分攻击。

对 $n=3$，性质“真值表恰有四个 $1$”可在扫描 $N=8$ 位后判定，并覆盖

的函数，因而既构造又很大。但它不对 P/poly 有用：常量规模或小型电路也能计算若干恰有四个真输入的函数。这个例子说明三条件彼此独立，满足“大且容易检查”远不足以给出下界。反过来，性质“最小电路规模超过 $2^{n/2}$”由 Shannon 计数可知对随机函数具有趋近 $1$ 的密度，并且它排除所有多项式规模族，因而对 P/poly 有用；是否能从 $2^n$ 位真值表在多项式时间判定这一性质并不知道，构造性正是缺口。若阈值只写成 $n^{100}$，最多直接得到对固定类 $\mathrm{SIZE}(n^{100})$ 的有用性，不能代表整个 P/poly。

密码学假设的强度也不能省略。普通多项式时间安全的单向函数可导出通常意义的 PRF，但自然性质判定器用时是 $\mathrm{poly}(2^n)$，远大于 $\mathrm{poly}(n)$；原障碍需要与这一真值表尺度相匹配的指数级安全参数。若没有相应强 PRF，结论只是没有可用的条件前提，而不是自然证明自动存在。

障碍不排除失败于任一条件的路线：性质可以很稀、不可构造，或针对不含强 PRF 的受限类。单调近似下界公理库Razborov 近似法Razborov approximation method · Method of approximations用简单函数近似单调电路的每个门并累计受控误差，从而推出规模下界。正处于受限模型中，不能因“Razborov”同名就误认为被 Razborov–Rudich 定理否定。

自然证明障碍解释了为何把 switching lemma、低次多项式或相关界机械加强，未必能一路推到一般电路下界：若加强后仍产生大、可从真值表有效识别且排除 P/poly 的性质，它会破坏强伪随机函数。研究路线因此转向几何复杂度、证明复杂度、元复杂度、稀有性质或算法导出下界等可能避开至少一项条件的方法。

其中Circuit-SAT 算法路线公理库电路可满足性问题Circuit satisfiability problem · Circuit-SAT给定编码后的布尔电路，判断是否存在输入赋值使其输出为真的 NP 完全问题。形成鲜明对照：它不先构造一个接受大量随机函数的真值表性质，而是用对受限电路可满足性的非平凡算法结合时间层级定理，反推出某个高复杂度类没有小电路。两条路线都研究下界为何困难，却一个给出条件性屏障，一个提供在精确闭包假设下的算法—下界桥梁。