Počet záznamů: 1
Fragments of approximate counting
- 1.
SYSNO ASEP 0433869 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Fragments of approximate counting Tvůrce(i) Buss, S.R. (US)
Kolodziejczyk, L. A. (PL)
Thapen, Neil (MU-W) RID, SAIZdroj.dok. Journal of Symbolic Logic. - : Cambridge University Press - ISSN 0022-4812
Roč. 79, č. 2 (2014), s. 496-525Poč.str. 30 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova approximate counting ; bounded arithmetic ; ordering principle Vědní obor RIV BA - Obecná matematika CEP IAA100190902 GA AV ČR - Akademie věd Institucionální podpora MU-W - RVO:67985840 UT WOS 000339939900007 EID SCOPUS 84925236312 DOI 10.1017/jsl.2013.37 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2015
Počet záznamů: 1