单调布尔电路

单调函数描述“增加资源不会破坏性质”：给图加边不会摧毁已有的团或连通路径，给集合加入元素不会让已达到的覆盖阈值失效。单调电路把这种语义忠实写入语法，每个门只会把更多的 $1$ 向输出传播。它不能先检测某条边缺失，再利用这个负信息重新组织计算；这项禁令正是单调下界能够远强于一般电路下界的来源。

语义单调与语法单调必须区分。一个一般电路可以带 NOT，经过抵消后仍计算单调函数；证明函数本身单调，并不能证明其所有电路都可删掉否定而保持相近规模。单调复杂度研究的核心问题正是：只用“正证据”要付出多少代价，而允许中间负信息时是否能显著压缩。

正证书多也不等于电路必然大。有向 $s$-$t$ 可达性可以把每条路径写成一个边变量合取，再对所有路径取 OR；简单路径数量可能指数增长。按允许的中间顶点做动态规划，却能共享“从 $u$ 到 $v$ 可达”的子判断，得到多项式大小的单调 DAG。因而可靠的单调下界必须排除跨证书共享，而不能只数朴素 DNF 的项。

在四个顶点的图上，以 $x_{ij}$ 表示边 $\{i,j\}$。含三角形的性质由单调公式

计算。共有四个候选三角形。若输入边集为 $\{12,13,23,34\}$，项 $\{1,2,3\}$ 的三条边全为 $1$，输出为 $1$；再增加边只会保留该项为真。若输入是四边形 $12,23,34,14$，每个三元组都缺至少一条弦，全部项为假。这个逐项轨迹同时展示了单调性和“证据是一组全存在的边”。

Parity 不是单调函数：$000$ 的 parity 为 $0$，$001$ 为 $1$，再把第二位升为 $1$ 得 $011$，输出回到 $0$，违反 $x\le y\Rightarrow f(x)\le f(y)$。因此它根本没有单调电路，而不是“单调电路很大”。相反，CLIQUE 是单调函数，但其朴素 DNF 可能极大；有没有更小的单调 DAG 是真正的单调电路复杂度理路单调电路复杂度Monotone circuit complexity · Monotone complexity在禁止否定的 AND/OR DAG 中最小化单调函数的门数与深度。问题。

边界还包括门权。使用非负权重的 threshold 门仍保持单调，允许负权重则可表达非单调中间判断；这不是同一门集。输入是否允许负文字也必须固定：一旦把 $\mathrm{\neg }{x}_i$ 当作免费输入，模型已越过本页的语法限制。

单调电路为图性质、组合优化可行性和数据库正查询提供结构模型。单调 CLIQUE 下界理路CLIQUE 的单调电路下界Monotone CLIQUE circuit lower bound · Razborov clique lower bound证明若干团大小参数下 CLIQUE 需要超多项式乃至指数规模的单调 AND/OR 电路。说明，即使目标性质有非常直接的正证据，把所有证据组织成小型 AND/OR DAG 仍可能需要超多项式规模。Razborov 近似法理路Razborov 近似法Razborov approximation method · Method of approximations用简单函数近似单调电路的每个门并累计受控误差，从而推出规模下界。正是利用门操作在正、负测试分布上的受控误差来证明这种困难。

单调 Karchmer–Wigderson 关系要求从真输入与假输入中找出 $x_i=1,y_i=0$ 的坐标，并刻画单调二元公式与电路的最小深度；详见KW 博弈理路Karchmer–Wigderson 博弈Karchmer-Wigderson game · KW game · Karchmer-Wigderson relation让一方持有真输入、另一方持有假输入并寻找分歧坐标的通信搜索关系。。在相同门基且不限制规模时，DAG 展开为公式会保留深度，却可能放大规模。KW 在这里控制深度，近似法则控制可共享的单调 DAG 规模，不能仅由上述深度下界宣称超多项式电路规模下界。