Počet záznamů: 1  

Total space in resolution

  1. 1. 0466751 - MU-W 2017 RIV US eng J - Článek v odborném periodiku
    Bonacina, I. - Galesi, N. - Thapen, Neil
    Total space in resolution.
    Siam Journal on Computing. Roč. 45, č. 5 (2016), s. 1894-1909. ISSN 0097-5397
    Grant CEP: GA ČR GBP202/12/G061
    GRANT EU: European Commission(XE) 339691 - FEALORA
    Institucionální podpora: RVO:67985840
    Klíčová slova: total space * resolution random CNFs * proof complexity
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 1.433, rok: 2016
    http://epubs.siam.org/doi/10.1137/15M1023269

    We 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.
    Trvalý link: http://hdl.handle.net/11104/0264987
    Název souboruStaženoVelikostKomentářVerzePřístup
    Thapen2.pdf3493.9 KBVydavatelský postprintvyžádat