On theories of bounded arithmetic for NC 1

Annals of Pure and Applied Logic 162 (4):322-340 (2011)
  Copy   BIBTEX

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

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2010.10.001

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,297

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

A sorting network in bounded arithmetic.Emil Jeřábek - 2011 - Annals of Pure and Applied Logic 162 (4):341-355.
Arithmetizing Uniform NC.Bill Allen - 1991 - Annals of Pure and Applied Logic 53 (1):1-50.
The canonical pairs of bounded depth Frege systems.Pavel Pudlák - 2021 - Annals of Pure and Applied Logic 172 (2):102892.
Polynomial size proofs of the propositional pigeonhole principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
An unexpected separation result in Linearly Bounded Arithmetic.Arnold Beckmann & Jan Johannsen - 2005 - Mathematical Logic Quarterly 51 (2):191-200.
Preservation theorems for bounded formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
Expander construction in VNC1.Sam Buss, Valentine Kabanets, Antonina Kolokolova & Michal Koucký - 2020 - Annals of Pure and Applied Logic 171 (7):102796.
Bounded arithmetic for NC, ALogTIME, L and NL.P. Clote & G. Takeuti - 1992 - Annals of Pure and Applied Logic 56 (1-3):73-117.
Implicit Proofs.Jan Krajíček - 2004 - Journal of Symbolic Logic 69 (2):387 - 397.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.

Analytics

Added to PP
2013-10-27

Downloads
40 (#565,712)

6 months
13 (#267,677)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Open induction in a bounded arithmetic for TC0.Emil Jeřábek - 2015 - Archive for Mathematical Logic 54 (3-4):359-394.
A sorting network in bounded arithmetic.Emil Jeřábek - 2011 - Annals of Pure and Applied Logic 162 (4):341-355.
Expander construction in VNC1.Sam Buss, Valentine Kabanets, Antonina Kolokolova & Michal Koucký - 2020 - Annals of Pure and Applied Logic 171 (7):102796.
Induction rules in bounded arithmetic.Emil Jeřábek - 2020 - Archive for Mathematical Logic 59 (3-4):461-501.

View all 6 citations / Add more citations

References found in this work

Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Bounded arithmetic for NC, ALogTIME, L and NL.P. Clote & G. Takeuti - 1992 - Annals of Pure and Applied Logic 56 (1-3):73-117.
A sorting network in bounded arithmetic.Emil Jeřábek - 2011 - Annals of Pure and Applied Logic 162 (4):341-355.

View all 7 references / Add more references