On theories of bounded arithmetic for NC1

0353280 - MÚ 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. E-ISSN 1873-2461
Grant CEP: GA AV ČR IAA1019401; GA MŠMT(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