论文标题
常规分辨率平均很难
Clique Is Hard on Average for Regular Resolution
论文作者
论文摘要
我们证明，对于$ k \ ll \ sqrt [4] {n} $常规分辨率需要长度$ n^{ω（k）} $，以确定具有适当选择的边缘密度的erdős-rényi图不包含$ k $ clique。该下限是指数中最佳的乘法常数，这也意味着无条件的$ n^{ω（k）} $在运行时间的下限中，几种最先进的算法都可以在图中找到最大的cliques。
We prove that for $k \ll \sqrt[4]{n}$ regular resolution requires length $n^{Ω(k)}$ to establish that an Erdős-Rényi graph with appropriately chosen edge density does not contain a $k$-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional $n^{Ω(k)}$ lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.
