Fragments of approximate counting
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Fragments of approximate counting
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Fragments of approximate counting
Popis výsledku anglicky
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.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/IAA100190902" target="_blank" >IAA100190902: Matematická logika, složitost a algoritmy</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2014
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Journal of Symbolic Logic
ISSN
0022-4812
e-ISSN
—
Svazek periodika
79
Číslo periodika v rámci svazku
2
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
30
Strana od-do
496-525
Kód UT WoS článku
000339939900007
EID výsledku v databázi Scopus
—