CLIQUE 的单调电路下界

形式陈述

在 $n$ 个顶点的简单图上，以 $\binom n2$ 个边变量为输入，定义

\mathrm{CLIQUE}_{n,k}(G)=1 \quad\Longleftrightarrow\quad G\text{ 含有一个 }k\text{ 顶点团}.

这里的团是两两相连的顶点集；增加边不会摧毁既有团，所以函数单调。Razborov 1985 年定理的一个方便、保守的参数化推论是：存在绝对常数 $c_0,c_1>0$ ，当 $3\le k\le c_0\log n$ 且 $n$ 足够大时，

C_+(\mathrm{CLIQUE}_{n,k})\ge n^{c_1k}.

原证明的底层估计形如 $n^k/(k^3e^k\ln n)^{2k}$ ，所以只有在注明 $k$ 的增长速度后，才能把分母吸收到指数常数中。特别地，取 $k=\Theta(\log n)$ 且比例常数足够小，得到 $n^{\Omega(\log n)}$ 的超多项式下界；对固定 $k$ ，则得到接近枚举上界的 $\Omega(n^k/(\log n)^{2k})$ 型界，隐常数依赖 $k$ 。Alon–Boppana 的改进进一步在

k=\left\lfloor\left(\frac{n}{8\log n}\right)^{2/3}\right\rfloor

附近得到

\exp\!\left(\Omega((n/\log n)^{1/3})\right)

的单调规模下界。这里的 $n$ 始终是顶点数，输入变量数是 $N=\binom n2$ ；若改用 $N$ 参数，指数中的幂也要随之换算。每个式子的 $k(n)$ 区间都是结论的一部分。

直觉

真输入可由某个 $k$ 元顶点集的全部 $\binom k2$ 条边作证，但可能证书数量极多且彼此重叠。单调电路只能用 AND 拼合必需边、用 OR 合并候选证书；它可以共享中间片段，却不能询问某条边缺失来排除一大批候选。Razborov 近似法证明，若门数太少，每个中间门都可由小团指标的受控组合近似，最终代理无法同时接受随机植入的 $k$ 团并拒绝随机完全 $(k-1)$ 部图。

负测试图的选择很关键。完全 $(k-1)$ 部图必定没有 $k$ 团，因为任取 $k$ 个顶点总有两个落在同一部，而同部之间没有边；同时它又非常稠密，会欺骗只检查少量边的简单正证据。下界不是来自“负例很稀疏”，而是来自一对精心匹配的分布：正例有集中团结构，负例在局部看起来仍含许多小团。

例子与边界

当 $n=5,k=3$ 时，朴素单调 DNF 对十个三元顶点集各放一个三边合取：

\bigvee_{\{i,j,\ell\}\in\binom{[5]}3} (x_{ij}\land x_{i\ell}\land x_{j\ell}).

若边集含 $12,13,23,45$ ，项 $\{1,2,3\}$ 的三个输入全为 $1$ ，电路接受。完全二部图 $K_{2,3}$ 没有三角形：每个三元组至少含两个同部顶点，对应同部边为 $0$ ，所以十项全部失败。二元门实现时，每项需两个 AND，合并十项需九个 OR，共 $29$ 门；这个小计算是上界实例，并不是渐近下界的证明。

参数边界防止夸大结论。 $k=2$ 时函数只是所有边的 OR，有线性于输入数的电路； $k=n$ 时只需对全部边取 AND，同样容易。因此强下界不可能对所有 $k$ 同时成立。更重要的是，定理只限制单调复杂度：允许 NOT 的一般电路可以使用负信息，Razborov 的误差闭包不再适用。把 $k$ 作为输入编码的一部分会得到经典 CLIQUE 判定问题，但本页的电路族对每对 $(n,k)$ 固定函数，不能由单调下界推出 $P\ne NP$ 。

推论与应用

该定理是电路下界史上的分水岭：它首次对一个自然、显式的组合函数排除了多项式规模单调电路，并展示“局部近似加分布误差”能够穿透 DAG 的共享。后续工作改善参数、推广到匹配等单调性质，也催生了 proof complexity 与扩展公式中的相关下界技术。

同时，它清楚标出当前技术的边界。CLIQUE 的一般非一致电路是否需要超多项式规模远未由此解决；在一般模型中证明类似下界会触及自然证明障碍等深层困难。教材中应把“受限模型上的强定理”视为可复用的结构实验，而不是把门集限定藏在脚注里。

参考资料

A. A. Razborov, “Lower Bounds for the Monotone Complexity of Some Boolean Functions,” Soviet Mathematics Doklady 31, 1985, pp. 354–357.
Noga Alon and Ravi B. Boppana, “The Monotone Circuit Complexity of Boolean Functions,” Combinatorica 7(1), 1987, pp. 1–22, Theorems 3.9 and 3.16.
Stasys Jukna, Boolean Function Complexity: Advances and Frontiers, Springer, 2012, Ch. 9.

形式陈述 ​

反向链接

形式陈述