Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

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

RSS-Feed




Revision #2
Authors: Jan Krajicek
Accepted on: 28th November 2013 17:47
Downloads: 705
Keywords: 


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





Revision #1
Authors: Jan Krajicek
Accepted on: 21st November 2013 18:06
Downloads: 728
Keywords: 


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





TR13-156
Authors: Jan Krajicek
Publication: 15th November 2013 13:55
Downloads: 1395
Keywords: 


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.



ISSN 1433-8092 | Imprint