Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle

被引：3

作者：

Atserias, Albert ^{[1
]}

Mueller, Moritz ^{[2
]}

Oliva, Sergi ^{[1
]}

机构：

[1] Univ Politecn Cataluna, Barcelona, Spain

[2] Kurt Godel Res Ctr, Vienna, Austria

来源：

2013 IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC) | 2013年

基金：

奥地利科学基金会;

关键词：

RESOLUTION LOWER BOUNDS; RANDOM FORMULAS; PROOFS; COMPLEXITY; SIZE;

D O I：

10.1109/CCC.2013.20

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The relativized weak pigeonhole principle states that if at least 2n out of n(2) pigeons fly into n holes, then some hole must be doubly occupied. We prove that every DNF-refutation of the CNF encoding of this principle requires size 2 (log n)(3/2-epsilon) for every epsilon > 0 and every sufficiently large n. For its proof we need to discuss the existence of unbalanced low-degree bipartite expanders satisfying a certain robustness condition.

引用

页码：109 / 120

页数：12

共 26 条

[1]

[Anonymous], COMPUTATIONAL COMPLE

[2]

[Anonymous], PSEUDORANDOM G UNPUB

[3]

[Anonymous], IEEETRANSACTIONSONED, DOI DOI 10.1109/13.965782

[4]

[Anonymous], 2001, RANDOM GRAPHS