Publication at Faculty of Mathematics and Physics |
2015
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 F-p.