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Ω(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) [7] and Dantchev and Riis (2001) [5]. © 2010 Elsevier B.V. All rights reserved.
A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games / Olaf, Beyersdorff; Galesi, Nicola; Lauria, Massimo. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 110:23(2010), pp. 1074-1077. [10.1016/j.ipl.2010.09.007]
A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games
GALESI, NICOLA;LAURIA, MASSIMO
2010
Abstract
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Ω(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) [7] and Dantchev and Riis (2001) [5]. © 2010 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
