Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > $AC^0[P]$ FREGE SYSTEMS, PROOF COMPLEXITY:
Reports tagged with $AC^0[p]$ Frege systems, proof complexity:
TR13-156 | 15th November 2013
Jan Krajicek

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

Revisions: 2

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 ... more >>>




ISSN 1433-8092 | Imprint