On theories of bounded arithmetic for NC1

0353280 - MÚ 2011 RIV NL eng J - Journal Article
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
R&D Projects: GA AV ČR IAA1019401; GA MŠMT(CZ) 1M0545
Institutional research plan: CEZ:AV0Z10190503
Keywords : bounded arithmetic * circuit complexity * propositional translation
Subject RIV: BA - General Mathematics
Impact factor: 0.450, year: 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.
Permanent Link: http://hdl.handle.net/11104/0192570