Brent–Spira 公式深度约简

形式陈述

设 $F$ 是叶数为 $s\ge2$ 的二元 De Morgan 公式。Brent–Spira 平衡化的稳健表述是：存在与 $F$ 计算同一函数的公式 $F'$ ，使

D(F')=O(\log s),\qquad L(F')=s^{O(1)}.

常数只依赖固定的有限扇入门基。Spira 的布尔公式定理给出这一对数深度、至多多项式规模的保证；在允许共享中间结果的 DAG 版本中，Brent 式重构可保持 $O(s)$ 电路规模并取得 $O(\log s)$ 深度。二者必须分开：把共享 DAG 再展开成树可能复制子电路，所以“线性规模”不能不加说明地搬到公式结论中。

证明的树分隔引理是：一棵有 $s$ 个叶的二叉树存在子树 $B$ ，其叶数介于 $s/3$ 与 $2s/3$ 之间。把 $B$ 暂视为一个变量 $z$ ，令 $F_0,F_1$ 分别是以常量 $0,1$ 代替 $B$ 后、沿祖先链传播常量并化简的公式，则

F\equiv(\neg B\land F_0)\lor(B\land F_1).

当 $B=0$ 时选择器只留下 $F_0$ ，当 $B=1$ 时只留下 $F_1$ ，所以等式可逐值核验。式中的 $\neg B$ 看似把否定放在内部结点；在 De Morgan 门基中只需交换 $B$ 内的 AND/OR 并翻转叶文字，便得到同叶数的否定对偶树。常量化简是规模估计所需的一步：例如 $0\land A=0$ 、 $1\land A=A$ ，OR 的两条规则同理。因 $B$ 是真子树，至少能消去它与父门相接的那片常量叶；若整个余式塌成常量，只留一片叶。因此 $L(F_0),L(F_1)\le s-L(B)\le2s/3$ ，而非未化简时的 $s-L(B)+1$ 。

递归平衡 $B,F_0,F_1$ ；每条递归路径上的叶数按固定比例下降，故深度递推 $d(s)\le d(2s/3)+O(1)$ ，解为 $O(\log s)$ 。把 $B$ 的正、负两份树都如实计入，可用单调上界 $S(s)\le4S(2s/3)+O(1)$ 控制输出叶数，仍为 $s^{O(1)}$ 。这段选择器递推证明的是多项式规模公式结论；单纯合并两份 $B$ 并不足以由此推出线性总规模。前述 $O(s)$ DAG 界还需要 Brent 式重构或相应的树收缩论证。

直觉

普通结合律只能平衡一串全是 AND 或全是 OR 的表达式；混合门公式没有可随意旋转的结合律。Brent–Spira 构造改用“询问一个中等大小子公式的值”：若 $B=0$ 就走 $F_0$ ，若 $B=1$ 就走 $F_1$ 。这个选择器把一棵极不平衡的语法树切成若干恒定比例的小块，类似每次在书中间放书签，而不是从第一页逐行读到末尾。

对数深度来自比例缩小，不来自门能一次读无限多个输入。每层仍只使用常数扇入门；经过 $O(\log s)$ 次切分，任何根到叶路径都到达常数规模。规模代价来自同一 $B$ 同时出现在选择器的正、负分支，以及余式在递归中的复制。若允许电路共享，这些重复可指向同一结点；若要求结果仍是树，就必须把复制如实计入公式复杂度。

平衡分隔子树通过选择器恒等式拆成三个较小公式，并递归得到对数深度 — Brent–Spira 的平衡分隔与递归

例子与边界

链式公式

F_8=(((((((x_1\land x_2)\land x_3)\land x_4)\land x_5)\land x_6)\land x_7)\land x_8)

有 $8$ 个叶、深度 $7$ 。在此特殊例子中可直接用结合律改为

((x_1\land x_2)\land(x_3\land x_4)) \land((x_5\land x_6)\land(x_7\land x_8)),

叶数仍为 $8$ 、深度为 $3$ 。一般公式不能指望零代价；例如选中的子式若处在一层 AND、一层 OR 交错的上下文中，必须通过 $F_0,F_1$ 两个余式保持条件语义，而不是简单旋转树边。

结论依赖有限扇入与公式规模。若允许一个 $s$ 扇入门，深度本来就可能是 $1$ ，树的叶数—深度计数关系也不同。定理处理的是公式树，不声称任意大小为 $s$ 的一般 DAG 电路都能无条件压到 $O(\log s)$ 深；那样的普遍结论会消除许多真实的深度复杂性。它也只保持计算函数，不保持原语法、门出现次数或短路求值次序。

推论与应用

定理给出最小公式深度与最小叶规模的数量级联系。二元深度 $d$ 的公式至多有 $2^d$ 个叶，所以 $D(f)\ge\log_2 L(f)$ ；对一棵达到 $L(f)$ 的最小公式应用平衡化，又有 $D(f)=O(\log L(f))$ 。因此

D(f)=\Theta(\log L(f))

对 $L(f)\ge2$ 的非常值、非文字函数，这就在固定 De Morgan 门基和相应最小化定义下成立；常量和单个文字应直接按约定处理，而不把 $\log1=0$ 塞进渐近记号。这里比较的是两个分别取最小值的资源，不是说每棵公式本身都已平衡。

对函数族而言，多项式规模公式经平衡后落入非一致NC¹。反过来， $O(\log n)$ 深、有界扇入的多项式规模电路可从输出展开为多项式大小公式，二者共同给出 NC¹ 的公式刻画。算法上，这一结构也是并行求值表达式的基础；但若要得到 uniform NC¹，还须证明重构能由规定资源的一致生成器完成。

参考资料

P. M. Spira, “On Time-Hardware Complexity Tradeoffs for Boolean Functions,” Proceedings of the 4th Hawaii International Symposium on System Sciences, 1971, pp. 525–527.
Richard P. Brent, “The Parallel Evaluation of General Arithmetic Expressions,” Journal of the ACM 21(2), 1974, pp. 201–206.
Ingo Wegener, The Complexity of Boolean Functions, Wiley-Teubner, 1987, §4.1.

形式陈述 ​

反向链接

形式陈述