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

Russell Impagliazzo, Nathan Segerlind

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