Brent–Spira 公式深度约简

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

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

链式公式

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

叶数仍为 $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))$。因此

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

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