ECCC-Report TR13-156https://eccc.weizmann.ac.il/report/2013/156Comments and Revisions published for TR13-156en-usThu, 28 Nov 2013 17:47:17 +0200
Revision 2
| A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems |
Jan Krajicek
https://eccc.weizmann.ac.il/report/2013/156#revision2We 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.Thu, 28 Nov 2013 17:47:17 +0200https://eccc.weizmann.ac.il/report/2013/156#revision2
Revision 1
| A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems |
Jan Krajicek
https://eccc.weizmann.ac.il/report/2013/156#revision1We 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.Thu, 21 Nov 2013 18:06:25 +0200https://eccc.weizmann.ac.il/report/2013/156#revision1
Paper TR13-156
| A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems |
Jan Krajicek
https://eccc.weizmann.ac.il/report/2013/156We 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.Fri, 15 Nov 2013 13:55:15 +0200https://eccc.weizmann.ac.il/report/2013/156