collaborators

1 paper

cs.CC2003

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 polynomially simulate Nullstellensatz refutations modulo . Central to this is a new definition of reduc…