Fragments of approximate counting

0433869 - MÚ 2015 RIV US eng J - Journal Article
Buss, S.R. - Kolodziejczyk, L. A. - Thapen, Neil
Fragments of approximate counting.
Journal of Symbolic Logic. Roč. 79, č. 2 (2014), s. 496-525. ISSN 0022-4812. E-ISSN 1943-5886
R&D Projects: GA AV ČR IAA100190902
Institutional support: RVO:67985840
Keywords : approximate counting * bounded arithmetic * ordering principle
Subject RIV: BA - General Mathematics
Impact factor: 0.541, year: 2014
http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=9287274&fileId=S0022481213000376

We study the long-standing open problem of giving for all Sigma(b)(1) separations for fragments of bounded arithmetic in the relativized setting. Rather than considering the usual fragments defined by the amount of induction they allow, we study Jerabek's theories for approximate counting and their subtheories. We show that the for all Sigma(b)(1) Herbrandized ordering principle is unprovable in a fragment of bounded arithmetic that includes the injective weak pigeonhole principle for polynomial time functions, and also in a fragment that includes the surjective weak pigeonhole principle for FPNP functions. We further give new propositional translations, in terms of random resolution refutations, for the consequences of T-2(1) augmented with the surjective weak pigeonhole principle for polynomial time functions.
Permanent Link: http://hdl.handle.net/11104/0238073