Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 
 

 

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


Author: Jan Krajíček
Journal: Proc. Amer. Math. Soc. 143 (2015), 4951-4965
MSC (2010): Primary 03F20, 68Q17
DOI: https://doi.org/10.1090/S0002-9939-2015-12610-X
Published electronically: April 2, 2015
MathSciNet review: 3391052
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 $ {{\bf F}_p}$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03F20, 68Q17

Retrieve articles in all journals with MSC (2010): 03F20, 68Q17


Additional Information

Jan Krajíček
Affiliation: Faculty of Mathematics and Physics, Charles University, Sokolovská 83, Prague 8, CZ - 186 75, The Czech Republic
Email: krajicek@karlin.mff.cuni.cz

DOI: https://doi.org/10.1090/S0002-9939-2015-12610-X
Received by editor(s): November 12, 2013
Received by editor(s) in revised form: November 21, 2013, December 2, 2013, and July 27, 2014
Published electronically: April 2, 2015
Communicated by: Mirna Dzamonja
Article copyright: © Copyright 2015 American Mathematical Society