论文标题
随机图中的完美匹配与tseitin一样困难
Perfect Matching in Random Graphs is as Hard as Tseitin
论文作者
论文摘要
我们研究了证明在奇数顶点上稀疏的随机常规图的复杂性，并没有完美的匹配，并且涉及每个顶点的相关问题匹配了一些预先指定的次数。我们表明，这需要多项式演算中的学位$ω（n / \ log n）$的证明（在特征$ \ ne 2 $的字段上）和平方符号的总和，以及有界深度的弗里格证明系统中的指数尺寸。这解决了Razborov的问题，询问Lovász-Schrijver Secur System是否需要$ n^δ$ roughs来驳斥这些公式，以$δ> 0 $。结果是通过依靠可能具有独立感兴趣的拓扑嵌入定理的最坏情况来减少这些公式的平均案例减少。
We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times. We show that this requires proofs of degree $Ω(n / \log n)$ in the Polynomial Calculus (over fields of characteristic $\ne 2$) and Sum-of-Squares proof systems, and exponential size in the bounded-depth Frege proof system. This resolves a question by Razborov asking whether the Lovász-Schrijver proof system requires $n^δ$ rounds to refute these formulas for some $δ> 0$. The results are obtained by a worst-case to average-case reduction of these formulas relying on a topological embedding theorem which may be of independent interest.
