Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations

Simple item page
dc.creatorImpagliazzo, Russell
dc.creatorSegerlind, Nathan
dc.date2003-08-05
dc.date.accessioned2026-07-07T03:20:12Z
dc.date.available2026-07-07T03:20:12Z
dc.descriptionWe 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.
dc.description17 pages
dc.identifierhttps://arxiv.org/abs/cs/0308012
dc.identifierhttp://arxiv.org/abs/cs/0308012
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31741
dc.subjectComputational Complexity
dc.subjectLogic in Computer Science
dc.subjectF.4.1
dc.titleConstant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations
dc.typetext

Files

Collections

arXiv