Počet záznamů: 1  

Total space in resolution

  1. 1.
    SYSNO ASEP0466751
    Druh ASEPJ - Článek v odborném periodiku
    Zařazení RIVJ - Článek v odborném periodiku
    Poddruh JČlánek ve WOS
    NázevTotal space in resolution
    Tvůrce(i) Bonacina, I. (SE)
    Galesi, N. (IT)
    Thapen, Neil (MU-W) RID, SAI
    Zdroj.dok.Siam Journal on Computing - ISSN 0097-5397
    Roč. 45, č. 5 (2016), s. 1894-1909
    Poč.str.16 s.
    Jazyk dok.eng - angličtina
    Země vyd.US - Spojené státy americké
    Klíč. slovatotal space ; resolution random CNFs ; proof complexity
    Vědní obor RIVBA - Obecná matematika
    CEPGBP202/12/G061 GA ČR - Grantová agentura ČR
    Institucionální podporaMU-W - RVO:67985840
    UT WOS000387321500007
    EID SCOPUS85010644516
    DOI10.1137/15M1023269
    AnotaceWe show quadratic lower bounds on the total space used in resolution refutations of random $k$-CNFs over $n$ variables and of the graph pigeonhole principle and the bit pigeonhole principle for $n$ holes. This answers the open problem of whether there are families of $k$-CNF formulas of polynomial size that require quadratic total space in resolution. The results follow from a more general theorem showing that, for formulas satisfying certain conditions, in every resolution refutation there is a memory configuration containing many clauses of large width.
    PracovištěMatematický ústav
    KontaktJarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
    Rok sběru2017
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.