Resolution lower bounds for perfect matching principles
Resolution lower bounds for perfect matching principles
复制标题
完美匹配原则的分辨率下限
DOI：
10.1109/ccc.2002.1004336
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
A. Razborov
中科院分区：
文献类型：
--
作者：
A. Razborov
对于任意超图 H，令 PM(H) 为断言 H 包含完美匹配的命题公式。我们证明 PM(H) 的每个解析反驳都必须具有大小 exp((/spl Omega/(/spl delta/(H)//spl lambda/(H)r(H)(log n(H))(r(H)+log n(H))))，其中 n(H) 是顶点数，/spl delta/(H) 是顶点的最小度，r(H) 是顶点的最大尺寸边，/spl lambda/(H) 是与两个不同顶点相关的最大边数。对于普通图 G，我们的一般界限大大简化为 exp (/spl Omega/(/spl delta/(G)/(log n(G))/sup 2/)))。作为直接推论，函数式到鸽笼原理版本上的每个解析证明 - FPHP/sub n//sup m/ 必须具有大小 exp (/spl Omega/(n/(log m)/sup 2/)) （当鸽子 m 的数量无界时，其变为 exp (/spl Omega/(n/sup 1/3/))）。这反过来立即暗示了主电路/sub t/(f/sub n/) 的分辨率证明大小的 exp(/spl Omega/(t/n/sup 3/)) 下界，断言 n 个变量中的布尔函数 f/sub n/ 的电路大小大于 t。特别是分辨率不具备 NP /spl subne/ P/poly 的有效证明。这些结果以自然的方式与更一般的原理 M(U|H) 相关，断言 H 包含覆盖 U /spl sube/ V(H) 中所有顶点的匹配。
For an arbitrary hypergraph H let PM(H) be the propositional formula asserting that H contains a perfect matching. We show that every resolution refutation of PM(H) must have size exp((/spl Omega/(/spl delta/(H)//spl lambda/(H)r(H)(log n(H))(r(H)+log n(H)))), where n(H) is the number of vertices, /spl delta/(H) is the minimal degree of a vertex, r(H) is the maximal size of an edge, and /spl lambda/(H) is the maximal number of edges incident to two different vertices. For ordinary graphs G our general bound considerably simplifies to exp (/spl Omega/(/spl delta/(G)/(log n(G))/sup 2/))). As a direct corollary, every resolution proof of the functional onto a version of the pigeonhole principle onto - FPHP/sub n//sup m/ must have size exp (/spl Omega/(n/(log m)/sup 2/)) (which becomes exp (/spl Omega/(n/sup 1/3/)) when the number of pigeons m is unbounded). This in turn immediately implies an exp(/spl Omega/(t/n/sup 3/)) lower bound on the size of resolution proofs of the principle circuit/sub t/(f/sub n/) asserting that the circuit size of the Boolean function f/sub n/ in n variables is greater than t. In particular resolution does not possess efficient proofs of NP /spl subne/ P/poly. These results relativize, in a natural way, to more general principle M(U|H) asserting that H contains a matching covering all vertices in U /spl sube/ V(H).