### Revision(s):

__
Revision #2 to TR13-156 | 28th November 2013 17:47
__
#### A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems

**Abstract:**
We give a general reduction of lengths-of-proofs lower bounds for

constant depth Frege systems in DeMorgan language augmented by

a connective counting modulo a prime $p$

(the so called $AC^0[p]$ Frege systems)

to computational complexity

lower bounds for search tasks involving search trees branching upon

values of linear maps on the vector space of

low degree polynomials over the finite field with $p$ elements.

**Changes to previous version:**
Clarifying a step in the proof of 5.1.

__
Revision #1 to TR13-156 | 21st November 2013 18:06
__
#### A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems

**Abstract:**
We give a general reduction of lengths-of-proofs lower bounds for

constant depth Frege systems in DeMorgan language augmented by

a connective counting modulo a prime $p$

(the so called $AC^0[p]$ Frege systems)

to computational complexity

lower bounds for search tasks involving search trees branching upon

values of maps on the vector space of

low degree polynomials over the finite field with $p$ elements.

**Changes to previous version:**
Section 6 was revised.

### Paper:

__
TR13-156 | 15th November 2013 08:37
__

#### A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems

**Abstract:**
We give a general reduction of lengths-of-proofs lower bounds for

constant depth Frege systems in DeMorgan language augmented by

a connective counting modulo a prime $p$

(the so called $AC^0[p]$ Frege systems)

to computational complexity

lower bounds for search tasks involving search trees branching upon

values of linear maps on the vector space of

low degree polynomials over the finite field with $p$ elements.