A reduction of proof complexity to computational complexity for $A{C}^0[p]$ Frege systems

Jan Krajicek

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