Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Collapsing modular counting in bounded arithmetic and constant depth propositional proofs

Authors: Samuel R. Buss, Leszek Aleksander Kołodziejczyk and Konrad Zdanowski
Journal: Trans. Amer. Math. Soc. 367 (2015), 7517-7563
MSC (2010): Primary 03F20, 03F30, 03B05, 68Q15
Published electronically: February 26, 2015
MathSciNet review: 3391892
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Jeřábek introduced fragments of bounded arithmetic which are axiomatized with weak surjective pigeonhole principles and support a robust notion of approximate counting. We extend these fragments to accommodate modular counting quantifiers. These theories can formalize and prove the relativized versions of Toda's theorem on the collapse of the polynomial hierarchy with modular counting. We introduce a version of the Paris-Wilkie translation for converting formulas and proofs of bounded arithmetic with modular counting quantifiers into constant depth propositional logic with modular counting gates. We also define Paris-Wilkie translations to Nullstellensatz and polynomial calculus refutations. As an application, we prove that constant depth propositional proofs that use connectives AND, OR, and mod p gates, for $ p$ a prime, can be translated, with quasipolynomial increase in size, into propositional proofs containing only propositional formulas of depth three in which the top level is Boolean, the middle level consists of mod p gates, and the bottom level subformulas are small conjunctions. These results are improved to depth two by using refutations from the weak surjective pigeonhole principles.

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

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03F20, 03F30, 03B05, 68Q15

Retrieve articles in all journals with MSC (2010): 03F20, 03F30, 03B05, 68Q15

Additional Information

Samuel R. Buss
Affiliation: Department of Mathematics, University of California, San Diego, La Jolla, California 92093-0112

Leszek Aleksander Kołodziejczyk
Affiliation: Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland

Konrad Zdanowski
Affiliation: Faculty of Mathematics and Natural Sciences, Cardinal Stefan Wyszyński University, Wóycickiego 1/3, 01-938 Warszawa, Poland

Received by editor(s): September 1, 2012
Received by editor(s) in revised form: June 21, 2013
Published electronically: February 26, 2015
Additional Notes: The first author was supported in part by NSF grants DMS-1101228 and CCR-1213151. In the preliminary stages of this work, the second and third authors were supported by grant no. N N201 382234 of the Polish Ministry of Science and Higher Education. Most of this work was carried out while the second author was visiting the University of California, San Diego, supported by the Polish Ministry of Science and Higher Education programme “Mobilność Plus” with additional support from a grant from the Simons Foundation (#208717 to Sam Buss).
Article copyright: © Copyright 2015 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.