| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4662619 | Annals of Pure and Applied Logic | 2011 | 19 Pages |
Abstract
We develop an arithmetical theory and its variant , corresponding to “slightly nonuniform” . Our theories sit between and , and allow evaluation of log-depth bounded fan-in circuits under limited conditions. Propositional translations of -formulas provable in admit L-uniform polynomial-size Frege proofs.
Related Topics
Physical Sciences and Engineering
Mathematics
Logic
