A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games
In this note we show that the asymmetric Prover–Delayer game developed in Beyersdorff et al. (2010)  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Ω(nlogn) for the pigeonhole principle in tree-like Resolution. This gives a new and simpler proof of the same lower bound established by Iwama and Miyazaki (1999)  and Dantchev and Riis (2001) .
12 references, page 1 of 2
views in local repository
downloads in local repository
The information is available from the following content providers: