Fragments of approximate counting

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F14%3A00433869" target="_blank" >RIV/67985840:_____/14:00433869 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1017/jsl.2013.37" target="_blank" >http://dx.doi.org/10.1017/jsl.2013.37</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1017/jsl.2013.37" target="_blank" >10.1017/jsl.2013.37</a>

Result language
angličtina
Original language name
Fragments of approximate counting
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/IAA100190902" target="_blank" >IAA100190902: Mathematical logic, complexity, and algorithms</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)