Håstad switching lemma

形式陈述 ​

令 $F$ 是变量集合上的宽度至多 $k$ 的 DNF。随机限制 $\rho \sim {\mathcal{R}}_p$ 独立处理每个变量：以概率 $p$ 留为未赋值 $\ast$，以概率 $(1-p)/2$ 固定为 $0$，以同样概率固定为 $1$。记 $F\upharpoonright \rho$ 为代入固定值并化简后的函数，$DT(f)$ 为计算 $f$ 的最小决策树公理库决策树模型Decision-tree model · Comparison decision tree用查询节点、答案分支和输出叶刻画算法能够区分输入所需的信息深度。深度。Håstad switching lemma 的一个标准形式是

$${\text{Pr}}_{\rho \sim {\mathcal{R}}_p}[DT(F\upharpoonright \rho )\ge t]\le (5pk{)}^t.$$

对宽度 $k$ 的 CNF 可对偶地陈述。若 $5pk<1$，需要深度至少 $t$ 的概率随 $t$ 指数下降；当右侧大于 $1$ 时界虽正确但没有信息。本页固定独立 ${\mathcal{R}}_p$、宽度与常数 $5$ 这一版本，后续结论不得混入其他 restriction 分布的常数。

可核验的证明骨架如下。先为 DNF 固定项的顺序，建立 canonical decision tree：选择第一个尚未被判假的项，查询其所有未定变量，直到该项满足或被排除。若树深至少 $t$，截取规范路径上前 $t$ 个查询。编码引理把“坏限制 $\rho$ + 这段路径”单射编码成另一限制 ${\rho }^{\prime }$ 与每步至多 $5k$ 种辅助标记；${\rho }^{\prime }$ 把这 $t$ 个原本自由变量固定为使规范项推进的值。相对于乘积分布公理库概率分布Probability distribution · Law定义在可测空间上的概率测度；随机变量的律是由推前得到的一类分布。，释放一个固定变量为 $\ast$ 带来至多 $p$ 量级的权重比，故全部坏对象的概率质量至多 $(5pk{)}^t$。单射的逆过程按辅助标记恢复每轮选中的项、查询位置与原限制，排除了重复计数。

直觉 ​

窄 DNF 的每一项只观察少量变量。随机固定大多数变量后，许多项直接变假，幸存项也只留下少量自由位；canonical tree 因而通常很浅。“Switching”指受限 DNF 可由浅决策树表示，并可在叶上改写成小宽度 CNF，而不是把任意电路的 AND、OR 机械互换。

编码证明测量的是坏限制需要携带多少额外信息。若一条很长规范路径仍存活，就能用沿途赋值压缩其自由度；可逆编码说明这类限制在随机分布中所占质量必然很小。

例子与边界 ​

对 DNF

$$F=(x_1\wedge x_2)\vee (x_3\wedge x_4)\vee \cdots ,$$

一次限制若把某项两个变量都固定为 $1$，整个公式立刻成为常量 $1$；若每项至少有一个变量固定为 $0$，则成为常量 $0$。只有若干项恰好躲过这两种消除才需继续查询，自由变量比例 $p$ 越小，长查询链越罕见。

宽度条件不可省略。单个项若包含全部 $n$ 个变量，随机限制后仍可能留下约 $pn$ 个自由变量，不能用固定 $k$ 的界描述。独立限制也很关键：若分布刻意让某一整项的变量总是同时自由，乘积概率和编码权重比都会失效。

定理只保证对随机限制的高概率简化，不说原公式本身有浅决策树，也不直接给出 $A{C}^0$ 下界。应用到多层电路时必须逐层选择参数、控制所有门的失败概率，并确保最终仍留下足够多自由变量。

推论与应用 ​

Switching lemma 是小深度电路随机限制法的核心。对 $A{C}^0$ 从底层开始反复限制，可把一层窄 CNF/DNF 压成浅决策树，再吸收到相邻层；迭代后整个电路高度下降，而 parity 等函数在剩余自由变量上仍保持复杂。

完整技术证明的编码细节决定常数 $5$ 和 restriction convention。本页给出可追踪的单射骨架；若需要最优常数、multi-switching 或带偏分布版本，应单独陈述其概率空间与编码引理。

参考资料

• Johan Håstad, Computational Limitations of Small-Depth Circuits, MIT Press, 1987, Chs. 2–3.
• Paul Beame, “A Switching Lemma Primer,” University of Washington Technical Report UW-CSE-95-07-01, 1994.