Fragments of approximate counting

0433869 - MÚ 2015 RIV US eng J - Článek v odborném periodiku
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
Grant CEP: GA AV ČR IAA100190902
Institucionální podpora: RVO:67985840
Klíčová slova: approximate counting * bounded arithmetic * ordering principle
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.541, rok: 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.
Trvalý link: http://hdl.handle.net/11104/0238073