The ordering principle in a fragment of approximate counting

0437494 - MÚ 2015 RIV US eng J - Článek v odborném periodiku
Atserias, A. - Thapen, Neil
The ordering principle in a fragment of approximate counting.
ACM Transactions on Computational Logic. Roč. 15, č. 4 (2014), s. 29. ISSN 1529-3785. E-ISSN 1557-945X
Grant CEP: GA AV ČR IAA100190902; GA ČR GBP202/12/G061
Institucionální podpora: RVO:67985840
Klíčová slova: computational complexity * bounded arithmetic * propositional proof complexity
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.618, rok: 2014
http://dl.acm.org/citation.cfm?doid=2656934.2629555

The ordering principle states that every finite linear order has a least element. We show that, in the relativized setting, the surjective weak pigeonhole principle for polynomial time functions does not prove a Herbrandized version of the ordering principle over T12. This answers an open question raised in Buss et al. [2012] and completes their program to compare the strength of Jeřábek's bounded arithmetic theory for approximate counting with weakened versions of it.
Trvalý link: http://hdl.handle.net/11104/0241058