Počet záznamů: 1
The canonical pairs of bounded depth Frege systems
- 1.
SYSNO ASEP 0535773 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 canonical pairs of bounded depth Frege systems Tvůrce(i) Pudlák, Pavel (MU-W) RID, SAI Číslo článku 102892 Zdroj.dok. Annals of Pure and Applied Logic. - : Elsevier - ISSN 0168-0072
Roč. 172, č. 2 (2021)Poč.str. 41 s. Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova circuits ; complexity ; games ; proofs Vědní obor RIV BA - Obecná matematika Obor OECD Pure mathematics CEP GX19-27871X GA ČR - Grantová agentura ČR Způsob publikování Omezený přístup Institucionální podpora MU-W - RVO:67985840 UT WOS 000594715500007 EID SCOPUS 85092113495 DOI 10.1016/j.apal.2020.102892 Anotace The canonical pair of a proof system P is the pair of disjoint NP sets where one set is the set of all satisfiable CNF formulas and the other is the set of CNF formulas that have P-proofs bounded by some polynomial. We give a combinatorial characterization of the canonical pairs of depth d Frege systems. Our characterization is based on certain games, introduced in this article, that are parametrized by a number k, also called the depth. We show that the canonical pair of a depth d Frege system is polynomially equivalent to the pair (Ad+2,Bd+2) where Ad+2 (respectively, Bd+1) are depth d+1 games in which Player I (Player II) has a positional winning strategy. Although this characterization is stated in terms of games, we will show that these combinatorial structures can be viewed as generalizations of monotone Boolean circuits. In particular, depth 1 games are essentially monotone Boolean circuits. Thus we get a generalization of the monotone feasible interpolation for Resolution, which is a property that enables one to reduce the task of proving lower bounds on the size of refutations to lower bounds on the size of monotone Boolean circuits. However, we do not have a method yet for proving lower bounds on the size of depth d games for d>1. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2022 Elektronická adresa https://doi.org/10.1016/j.apal.2020.102892
Počet záznamů: 1