Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DNF-RESOLUTION:
Reports tagged with DNF-resolution:
TR13-116 | 29th August 2013
Albert Atserias, Moritz Müller, Sergi Oliva

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

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 ... more >>>

ISSN 1433-8092 | Imprint