Razborov 近似法

直接追踪电路的全部中间函数会立即失控：即使门数不多，每个门也可能代表庞大的图族。近似法给每个中间函数拍一张“低分辨率照片”，只保留小证书或低复杂度结构。AND、OR 后照片可能变复杂，便通过删减、闭包或 sunflower 规则压回允许的格式；每次压缩都会误认少量输入。小电路只能进行少量压缩，累计误差仍小，因此若目标函数在正负分布上需要比任何低分辨率照片更清晰的边界，小电路就不存在。

它与随机限制法公理库随机限制法Random restriction method · Random restrictions随机固定大部分输入，使受限电路结构简化而目标函数仍保留困难性的下界方法。的随机性落点不同：随机限制法随机固定输入，使原电路结构塌缩；近似法保留输入空间，却把门函数换成简单代理并统计误差。二者都用概率把“所有小电路”压成可控对象，但一个随机化实例，一个近似化表示，参数递推不能互抄。

在 CLIQUE 分析中，令

表示图 $G$ 含有顶点集 $A$ 上的完整团。正分布可取在随机 $k$ 元顶点集 $K$ 上只放置 $K_k$ 的图，则对 $|A|=r$，

例如 $n=8,k=4,r=2$ 时概率为 $6/28=3/14$。负分布可取随机着色产生的完全 $(k-1)$ 部图；同一 $T_A$ 为真要求 $A$ 的颜色两两不同，概率为 $(k-1{)}_r/(k-1{)}^r$，上述 $k=4,r=2$ 时是 $6/9=2/3$。一个小团指标竟常接受负例，说明单个简单项无法完成分离；证明要组织许多指标并用闭包与 sunflower 控制哪些误差可以累积。

这些数值不是完整下界证明，只展示分布为何有辨别力。参数 $r,k,n$、正例是否只含团边、负例的分部生成方式都会改变概率。近似法也不是“任何逐门近似都给下界”：若简单类过强，它本身就能表示目标；若过弱，单门误差太大，$s\epsilon$ 很快失去信息。矩阵秩、低次多项式等后续近似版本还有各自的域与误差定义，不能混成一个无参数口号。

Razborov 用该方法首次得到显式自然函数的超多项式单调电路下界，核心应用是CLIQUE公理库CLIQUE 的单调电路下界Monotone CLIQUE circuit lower bound · Razborov clique lower bound证明若干团大小参数下 CLIQUE 需要超多项式乃至指数规模的单调 AND/OR 电路。。Alon–Boppana 随后改进近似族与组合计数，取得特定参数区间的指数型界。方法还启发了对单调公式、切割平面以及通信问题的近似与矩阵技术，但每次迁移都要重新证明门运算的误差闭包。

这种成功与自然证明障碍公理库自然证明障碍Natural proofs barrier · Razborov-Rudich natural proofs在强伪随机函数假设下排除同时具备构造性、大性和有用性的一般电路下界性质。并不矛盾。近似法在受限单调模型中利用高度专门的正负分布；自然证明障碍则在强伪随机函数假设下排除对足够强一般电路类同时满足大性、构造性与有用性的性质。前者不能直接越过后者去证明一般 P/poly 下界，后者也没有否定已经成立的单调下界。