Regular resolution lower bounds for the weak pigeonhole principle (Q558246)

The paper is devoted to the study of the complexity of resolution proofs of the weak pigeonhole principle WPHP. It is shown that for any \(m\), any regular resolution proof for WPHP\(^{m}_{n}\) (i.e., weak pigeonhole principle with \(m\) pigeons and \(n\) holes) is of length \(\Omega (2^{n^{\epsilon}})\), where \(\epsilon > 0\) is some global constant.