Name
Title | ||
|---|---|---|
Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations |
Abstract | ||
|---|---|---|
We show that bounded-depth Frege systems with counting axioms modulo m polynomially simulate Nullstellensatz refutations modulo m. When combined with a previous result of the authors, this establishes the first size (as opposed to degree) separation between Nullstellensatz and polynomial calculus refutations. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/3-540-45465-9_19 | ICALP |
Keywords | Field | DocType |
polynomial calculus refutation,bounded-depth frege system,bounded-depth frege systems,axioms polynomially simulate nullstellensatz,previous result,m polynomially | Discrete mathematics,Combinatorics,Modulo,Axiom,Polynomial calculus,Mathematics,Bounded function | Conference |
ISBN | Citations | PageRank |
3-540-43864-5 | 0 | 0.34 |
References | Authors | |
14 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Russell Impagliazzo | 1 | 5444 | 482.13 |
| Nathan Segerlind | 2 | 223 | 11.22 |