|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 . Using a technique of Razborov  and simplified by Impagliazzo, Pudlak and Sgall , 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.
|Journal||Archive for Mathematical Logic|
|Pages||403 - 414|