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 |
|