Počet záznamů: 1
The provably total NP search problems of weak second order bounded arithmetic
- 1.
SYSNO ASEP 0359552 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 The provably total NP search problems of weak second order bounded arithmetic Tvůrce(i) Kolodziejczyk, L. A. (PL)
Thapen, Neil (MU-W) RID, SAI
Nguyen, Phuong (MU-W)Zdroj.dok. Annals of Pure and Applied Logic. - : Elsevier - ISSN 0168-0072
Roč. 162, č. 6 (2011), s. 419-446Poč.str. 28 s. Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova complexity ; fragments Vědní obor RIV BA - Obecná matematika CEP IAA100190902 GA AV ČR - Akademie věd LC505 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000289022500002 EID SCOPUS 79952006622 DOI 10.1016/j.apal.2010.12.002 Anotace We define a new NP search problem, the "local improvement" principle, about labellings of an acyclic, bounded-degree graph. We show that, provably in PV, it characterizes the for all Sigma(b)(1) consequences of V-2(1) and that natural restrictions of it characterize the for all Sigma(b)(1) consequences of U-2(1) and of the bounded arithmetic hierarchy. We also show that over V-0 it characterizes the for all Sigma(B)(0) consequences of V-1 and hence that, in some sense, a miniaturized version of the principle gives a new characterization of the for all Pi(b)(1) consequences of S-2(1). Throughout our search problems are "type-2" NP search problems, which take second-order objects as parameters: (c) 2011 Elsevier B.V. All rights reserved. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2012
Počet záznamů: 1