单调电路复杂度

单调规模衡量“只凭出现了什么”来认证性质的成本。每个 AND 门合并若干必须同时成立的正证据，每个 OR 门在替代证据间选择；DAG 允许证据片段共享。一个下界要证明，无论怎样共享，小量正证据都无法覆盖全部真输入而避开全部假输入。这个任务比指出朴素 DNF 有很多项困难，因为电路可能用多层中间概念大量复用。

与一般电路比较时，应把限制理解为信息纪律而非硬件缺陷。NOT 门允许电路暂时表达“某种候选结构不存在”，再把许多候选的失败模式合并；单调电路不能利用这种中间负信息。Tardos 等人的分离结果表明，这种纪律在某些显式函数上确实产生巨大成本，但它不意味着所有单调函数都困难：阈值、可达性的某些参数化版本和许多动态规划都有紧凑单调构造。

函数 ${\mathrm{THR}}_{n,k}(x)$ 在至少 $k$ 个输入为 $1$ 时输出 $1$。定义 $g_{i,j}$ 表示前 $i$ 位至少有 $j$ 个 $1$，取边界 $g_{i,0}=1$，以及 $j>i$ 时 $g_{i,j}=0$（特别地 $g_{0,j}=0$ 对 $j>0$ 成立），并递推

递推的两项划分成功原因：前 $i-1$ 位已经够 $j$ 个，或者第 $i$ 位为 $1$、此前已经够 $j-1$ 个；二者可能同时成立，但 OR 不会重复计数。边界 $j>i$ 为零尤其重要，例如计算 $g_{1,1}$ 时出现的 $g_{0,1}$ 必须解释为不可能状态。

只需保留 $1\le j\le min(i,k)$ 的状态，非平凡状态不超过 $nk$ 个；每个状态至多增加一个 AND 和一个 OR，所以在化简常量前也不超过 $2nk$ 个门。对 $n=4,k=2$ 和输入 $1010$，先有 $g_{1,1}=1$；读到第二位后 $g_{2,2}=0$；第三位为 $1$，故 $x_3\wedge g_{2,1}=1$，得到 $g_{3,2}=1$，最终 $g_{4,2}=1$。同一 $g_{i,j}$ 被多个后继复用；若从 $g_{n,k}$ 递归展开成树，通往边界状态的分支数会出现二项式系数，$k$ 与 $n$ 同阶时朴素展开可达指数规模。

这个上界不自动最优，也不适用于带负权的线性阈值函数。输入个数增加、目标阈值固定时，可以把每个阶段不再使用的状态擦除来节约顺序算法的内存，但电路模型记录整张展开的 DAG；不能把滚动数组的 $O(k)$ 存储界误称为 $O(k)$ 电路门数。若函数不是单调，$C_{+}(f)$ 通常视为无穷或未定义，而不是一个很大的有限数。模型还必须固定 fan-in：无界 OR 可把所有最小证书一层汇总，二元 OR 需要额外对数深度和线性数量门。规模下界与深度下界也不能互换；一张大而浅的单调电路可能与小而深的电路计算同一函数。最后，极小 $1$ 输入很多只说明规范 DNF 很长；上面的状态共享正展示了为何证书计数本身不是 $C_{+}$ 下界。

单调复杂度是少数能对自然显式函数证明强电路下界的领域。Razborov 近似法公理库Razborov 近似法Razborov approximation method · Method of approximations用简单函数近似单调电路的每个门并累计受控误差，从而推出规模下界。把每个中间门替换为受控的简单近似，证明小电路的最终近似不可能同时在正例与反例分布上正确；应用到图团得到CLIQUE 单调下界公理库CLIQUE 的单调电路下界Monotone CLIQUE circuit lower bound · Razborov clique lower bound证明若干团大小参数下 CLIQUE 需要超多项式乃至指数规模的单调 AND/OR 电路。。这些结果解释受限模型的结构，却不解决一般布尔电路下界。

它也为算法设计提供反面诊断。上面的计数动态规划显示，有界阈值可通过状态共享得到小单调电路；若某个算法只合并正证书，就可把其状态转移直接翻译成单调 DAG，从而由已知下界排除过小的此类算法。反过来，一个一般多项式时间算法使用否定、取消或代数消去时，不能只凭输出性质单调就套用单调下界。