0437494 - MÚ 2015 RIV US eng J - Journal Article
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
R&D Projects: GA AV ČR IAA100190902; GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : computational complexity * bounded arithmetic * propositional proof complexity
Subject RIV: BA - General Mathematics
Impact factor: 0.618, year: 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.
Permanent Link: http://hdl.handle.net/11104/0241058