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 
