布尔公式复杂度

规模问“为了写出所有必要的证据，变量要在语法树中出现多少次”，深度问“沿最坏依赖链要连续作多少次选择”。一棵公式可以用很多彼此并行的分支换取浅深度，也可以把同样数量的门串成一条长链。由于没有共享，某个中间判断若被不同情形反复调用，其整段推导会反复出现在叶计数中；这正是公式复杂度与电路规模和深度理路电路规模与深度Circuit size and depth分别计数门数和最长输入到输出路径长度的电路资源度量。既相似又不相同的地方。

研究最小公式而非某个随手写出的公式，是为了把“表达方式笨拙”与“函数本身困难”分开。真值表 DNF 给每个接受输入一个完整项，通常产生 $O(n{2}^n)$ 个叶，只是通用上界；证明下界必须排除所有代数化简、重新括号化和不同门组合，而不是指出这一份 DNF 很长。博弈、随机限制和矩阵方法的价值，正是把“所有可能公式”压缩为可追踪的不变量。

二位异或

给出 $L(x\oplus y)\le 4$。事实上少于四个文字叶不够。若公式中 $x$ 只以正文字出现，那么固定 $y$ 后，输出关于 $x$ 单调不减；若只出现 $\mathrm{\neg }x$，则单调不增。异或却在 $y=0$ 时随 $x$ 从 $0$ 变 $1$，在 $y=1$ 时沿相同变化从 $1$ 变 $0$，所以 $x$ 的两种极性都必须出现。对 $y$ 同理，至少需要 $x,\mathrm{\neg }x,y,\mathrm{\neg }y$ 四个叶。这个论证排除了所有三叶公式，而不只排除某种括号写法。

再看 $A_n=x_1\wedge \cdots \wedge x_n$。链式括号 $(((x_1\wedge x_2)\wedge x_3)\cdots )$ 有 $n$ 个叶、深度 $n-1$；平衡二叉树仍有 $n$ 个叶，深度降为 $\lceil {\log }_{2}n\rceil$。这里利用了 AND 的结合律，不能据此断言任意混合门公式都可原规模重排。对一般公式，Brent–Spira 定理理路Brent–Spira 公式深度约简Brent depth reduction theorem · Spira theorem · Formula balancing theorem将任意有限扇入布尔公式在多项式规模内平衡到关于原规模的对数深度。需要更精细的子公式分隔与选择器构造。

公式大小还依赖输入表示。把一个 $2^n$ 位真值表视为输入，和把 $n$ 个变量视为输入是不同问题；允许 XOR 原子门会把上面的四叶异或压成一门。部分函数只要求在承诺域上正确，也可能比其任意全域扩张更小。任何下界都应同时标出门基、扇入、规模 convention 与函数是否为全函数。

多项式叶规模公式族在非一致意义下恰好对应NC¹理路复杂性类 NC¹NC1 · NC^1 · Nick's Class level one由多项式规模、有界扇入且对数深度的布尔电路族计算的第一层 NC。：一边由公式平衡化得到多项式规模、$O(\log n)$ 深度；另一边把有界扇入、$O(\log n)$ 深电路从输出向输入展开，至多产生 $2^{O(\log n)}=n^{O(1)}$ 个叶。若要得到统一算法，还须另证一致性理路电路族一致性Circuit family uniformity要求输入长度 n 对应电路可由统一算法有效生成的条件。；非一致函数族也能作为语言的逐长度特征函数，不能仅因讨论对象叫作语言就自动获得生成算法。

下界工具从不同方向观察同一最小化问题。公式规模博弈理路公式规模博弈Formula-size game · Propositional formula-size game · EF_w formula game以正反例集合的左右分割和叶预算精确刻画命题公式的最小叶规模。把每个 AND/OR 结点变成对负例集或正例集的分割；Karchmer–Wigderson 博弈理路Karchmer–Wigderson 博弈Karchmer-Wigderson game · KW game · Karchmer-Wigderson relation让一方持有真输入、另一方持有假输入并寻找分歧坐标的通信搜索关系。把根到叶路径变成通信 transcript，分别突出叶数和深度。两种刻画相互补充，却不是把同一个游戏换名复制。