Počet záznamů: 1

On theories of bounded arithmetic for NC1

  1. 1.
    0353280 - MU-W 2011 RIV NL eng J - Článek v odborném periodiku
    Jeřábek, Emil
    On theories of bounded arithmetic for NC1.
    Annals of Pure and Applied Logic. Roč. 162, č. 4 (2011), s. 322-340 ISSN 0168-0072
    Grant CEP: GA AV ČR IAA1019401; GA MŠk(CZ) 1M0545
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: bounded arithmetic * circuit complexity * propositional translation
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 0.450, rok: 2011
    http://www.sciencedirect.com/science/article/pii/S0168007210001260

    We develop an arithmetical theory VNC1 and its variant VNC1, corresponding to "slightly nonuniform" NC1. Our theories sit between VNC1 and VL, and allow evaluation of log-depth bounded fan-in circuits under limited conditions. Propositional translations of -formulas provable in VNC1 admit L-uniform polynomial-size Frege proofs.
    Trvalý link: http://hdl.handle.net/11104/0192570
    Název souboruStaženoVelikostKomentářVerzePřístup
    Jerabek1.pdf1361 KBVydavatelský postprintvyžádat