Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR10-081 | 10th May 2010 17:00

#### A Lower Bound for the Pigeonhole Principle in Tree-like Resolution by Asymmetric Prover-Delayer Games

TR10-081
Authors: Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
Publication: 10th May 2010 19:08
Downloads: 2104
Keywords:

Abstract:

In this note we show that the asymmetric Prover-Delayer game developed by Beyersdorff, Galesi, and Lauria (ECCC TR10-059) for Parameterized Resolution is also applicable to other tree-like proof systems. In particular, we use this asymmetric Prover-Delayer game to show a lower bound of the form \$2^{\Omega(n\log n)}\$ for the pigeonhole principle in tree-like Resolution. This gives a new and simpler proof of the same lower bound established by Dantchev and Riis (CCC'01).

ISSN 1433-8092 | Imprint