随机限制法

浅 AND/OR 电路常依赖许多“脆弱的局部条件”。随机固定大部分变量后，一个被固定为 $0$ 的文字就能杀死合取项，一个被固定为 $1$ 的文字就能满足析取项，大量分支随之消失。目标函数若具有稳健的全局依赖，例如 parity 对每个自由变量仍敏感，就不会以同样速度塌缩。限制像把复杂装置的大部分旋钮封死，再比较剩余装置和目标是否同样容易操作。

随机性只服务证明，不把电路改成随机算法。最终结论通常是确定性的：“不存在某种大小和深度的电路。”证明者随机抽取 $\rho$，只是用正概率证明至少存在一个同时具有两种性质的限制。参数 $p$ 太大，电路不够简化；太小，目标几乎没有自由变量。真正的工作是让这两种概率窗口重叠。

令

代入后第一项变为 $x_2$，第二项因 $x_3=0$ 变为 $0$，所以 $F\upharpoonright \rho =x_2$，一张两项 DNF 塌成深度 $1$ 的决策。对四位 parity，同一限制给出

它仍同时依赖两个自由变量。这个可复算对照展示“电路局部项被决定、目标保留敏感性”的机制；完整下界还要让同一个随机限制同时简化多项式多个门。

高概率简化不表示每个限制都好。取 $\rho =(\ast ,\ast ,\ast ,\ast )$ 时上式完全未简化；刻意让整项变量总是一起自由的相关分布也可能破坏 switching lemma 的乘积权重计算。对一层门的成功概率不能直接乘成全电路成功率，通常要作 union bound，并让单门失败概率远小于门数倒数。逐层限制还要追踪条件分布，不能假定每轮重新独立抽样而不证明等价。

目标是否存活也要定量检查。在 ${\mathcal{R}}_p$ 下，自由变量数 $U$ 服从 $\mathrm{Bin}(n,p)$，故 $\mathbb{E}U=pn$，并有 Chernoff 界

当 $pn$ 仍趋于无穷时，parity 以高概率保留许多真正自由的坐标；只说“平均还剩一些变量”不足以与电路简化事件取交。

随机限制法给出parity 不属于 AC⁰公理库Parity 不属于 AC⁰Parity not in AC0 · AC0 parity lower bound证明任何多项式规模、常数深度、无界扇入 AND/OR/NOT 电路族都不能计算奇偶函数。及其定量加强：受限 AC⁰ 经过逐层 switching 变成浅决策树，而受限 parity 仍需查询所有自由位。它也用于相关界、伪随机性、学习理论和证明复杂度；更强的 multi-switching lemma 能一次控制公式族，但有不同概率界，应单独引用。

与Razborov 近似法公理库Razborov 近似法Razborov approximation method · Method of approximations用简单函数近似单调电路的每个门并累计受控误差，从而推出规模下界。相比，本方法随机改变输入、保留原门语义；近似法固定输入分布、改变中间函数表示。两者都把小电路转成简单对象，却有不同的误差累计和失败边界。自然证明视角还表明，许多这类组合下界在真值表尺度上具有构造性和大性；这不影响它们对 AC⁰ 的有效性，但提醒人们不能机械外推到一般 P/poly。