Details:

Title	Degree Complexity for a Modified Pigeonhole Principle
Author(s)	Maria Luisa Bonet, Nicola Galesi
Type	Technical Report, Misc
Abstract	We consider a modification of the pigeonhole principle, MPHP, introduced by Goerdt in [7]. Using a technique of Razborov [9] and simplified by Impagliazzo, Pudlak and Sgall [8], we prove that any Polynomial Calculus refutation of a set of polynomials encoding the MPHP, requires degree Omega (log n). We also prove that the this lower bound is tight, giving Polynomial Calculus refutations of MPHP of optimal degree. Finally, we prove a simple Lemma giving a simulation of Resolution by Polynomial Calculus.
Length	13
File
Language	English
Journal	Archive for Mathematical Logic
Volume	42
Number	5
Pages	403 - 414
Year	2003
Edition	0
Translation	No
Refereed	No