Loading...
Please wait, while we are loading the content...
Similar Documents
Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations
| Content Provider | arXiv |
|---|---|
| Author | Impagliazzo, Russell Segerlind, Nathan |
| Date of Submission | 2003-08-05 |
| Abstract | We show that constant-depth Frege systems with counting axioms modulo $m$ polynomially simulate Nullstellensatz refutations modulo $m$. Central to this is a new definition of reducibility from formulas to systems of polynomials with the property that, for most previously studied translations of formulas to systems of polynomials, a formula reduces to its translation. When combined with a previous result of the authors, this establishes the first size separation between Nullstellensatz and polynomial calculus refutations. We also obtain new, small refutations for certain CNFs by constant-depth Frege systems with counting axioms. |
| Related Links | https://arxiv.org/pdf/cs/0308012.pdf |
| Page Count | 17 |
| arXiv | cs/0308012 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Computational Complexity Computer Science - Logic in Computer Science Mathematical Logic Computer Science |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |
