Håstad switching lemma

形式陈述 ​

令 $k,t\ge 1$ 为整数，$F$ 是有限变量集上的DNF理路析取范式Disjunctive normal form · DNF由文字的合取形成项，再对这些项取析取得到的命题公式形状。，每个合取项最多含 $k$ 个文字。先删除矛盾项和重复文字。对 $0\le p\le 1$，随机限制 $\rho \sim {\mathcal{R}}_p$ 独立处理每个变量：以概率 $p$ 留为未赋值 $\ast$，以概率 $(1-p)/2$ 固定为 $0$，以同样概率固定为 $1$。记 $F\upharpoonright \rho$ 为代入固定值并化简后的函数，$DT(f)$ 为每次查询一个自由变量、计算 $f$ 的最小决策树理路决策树模型Decision-tree model用查询节点、答案分支和输出叶刻画算法能够区分输入所需的信息深度。深度，常量函数的深度为 $0$。Håstad switching lemma 的一个标准形式是

对宽度 $k$ 的 CNF 可对偶地陈述。若 $5pk<1$，需要深度至少 $t$ 的概率随 $t$ 指数下降；当右侧大于 $1$ 时界虽正确但没有信息。本页的定理固定独立 ${\mathcal{R}}_p$、宽度与常数 $5$ 这一版本；下面另用同一分布下的较弱界展示编码，明确区分两个常数。

编码证明应把组合计数与概率权重分开。先固定 DNF 项的顺序，建立 canonical decision tree：选择第一个尚未被判假的项，查询其所有未定变量；若项满足则输出 $1$，否则继续寻找下一项，所有项均假时输出 $0$。最小决策树深度不超过这棵具体树的深度，因此控制规范树的长路径足以控制定理中的坏事件。

对每个坏限制，按固定顺序选取一条至少长 $t$ 的路径，截取前 $t$ 个查询。将这些自由变量固定为与当轮所选项一致的值，得到限制 ${\rho }^{\prime }$。辅助信息记录变量在项内的位置、每轮的结束位置，以及原路径上的回答；这些信息让解码器逐轮恢复原路径，并把改过的变量重新释放为 $\ast$。路径必须按确定规则选取，否则会额外重复计算同一个坏限制。

若恰好固定 $t$ 个自由变量，对 $0<p<1$，乘积分布理路概率分布Probability distribution · Law可测空间上总质量为一的测度；随机变量的律是由样本概率推出的一类分布。给出的精确权重比是

不能把每一步的比值直接写成 $p$。例如 Thapen 的显式编码用至多 $(2k{)}^t$ 种位置及分段标记和 $2^t$ 种回答串，得到 $(8pk/(1-p){)}^t$；在 $p<1/9$ 时可上界为 $(9pk{)}^t$。这是同一简化机制的较弱界，不是上面常数 $5$ 的证明。要得到标准 $(5pk{)}^t$，需使用对应版本中更精细的证明与估计，不能把“每步若干标记”和“$p$ 量级”机械相乘就宣称常数已经验证。