Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed




TR10-081
Authors: Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
Publication: 10th May 2010 19:08
Downloads: 4215
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