Random CNF's are Hard for the Polynomial Calculus
| Author(s) : | Russell Impagliazzo Eli Ben-sasson, |
| Publisher : | N/A |
| Publication Date : | 1999 |
| ISSN : | N/A |
| Abstract : | We show a general reduction that derives lower bounds on degrees of polynomial calculus proofs of tautologies over any field of characteristic other than 2 from lower bounds for resolution proofs of a related set of linear equations modulo 2. We apply this to derive linear lower bounds on the degrees of PC proofs of randomly generated tautologies. 1., |