A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games

作者：Beyersdorff Olaf^*; Galesi Nicola; Lauria Massimo

来源：Information Processing Letters, 2010, 110(23): 1074-1077.

DOI：10.1016/j.ipl.2010.09.007

• Computational complexity
• Proof complexity
• Prover-Delayer games
• Resolution

In this note we show that the asymmetric Prover-Delayer game developed in Beyersdorff et al. (2010) [2] 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 Iwama and Miyazaki (1999) [7] and Dantchev and Riis (2001) [5].

• 出版日期2010-11-15