随机 (log n)-CNF 公式对带模门的深度-2 Frege 系统是困难的
Random ($\log{n}$)-CNF Formulas Are Hard for Depth-$2$ Frege with Modular Gates
Jonas Conneryd
AI 速读 基于摘要
作者证明随机 k-CNF（k 在 ω_n(1) 到 O(log n) 之间）需要多项式演算度数至少 n/2−O(n/√k)，并借助 Pang 的权衡关系推出深度-2 AC^0[p]-Frege 的指数下界。
cs.CC
查看原文摘要
We prove that, with high probability, refuting a random $k$-CNF formula on $n$ variables with ${M = n2^{k}}$ clauses for $ω_n(1) \leq k \leq O(\log{n})$ requires polynomial calculus degree at least ${n/2-O(n/\sqrt{k})}$ over every field. Through Pang's recent tradeoff between $\mathsf{AC}^0[p]$-Frege size and polynomial calculus degree [Pang 2026, arXiv:2610.00837v2], this implies a size lower bound of $\exp(Ω_p(\sqrt{k} \log{n}))$ for depth-$2$ $\mathsf{AC}^0[p]$-Frege. In this range of $k$, the bound is superpolynomial in $M$ while $M \leq \mathrm{poly}(n)$. We also prove a nearly matching degree upper bound of $n/2-n\ln(k)/{2k} +O(n/k)$, which shows that other formula families are needed to obtain lower bounds for full $\mathsf{AC}^0[p]$-Frege through Pang's tradeoff.