Bounded arithmetic for NC, ALogTIME, L and NL

Annals of Pure and Applied Logic 56 (1-3):73-117 (1992)
  Copy   BIBTEX

Abstract

We define theories of bounded arithmetic, whose definable functions and relations are exactly those in certain complexity classes. Based on a recursion-theoretic characterization of NC in Clote , the first-order theory TNC, whose principal axiom scheme is a form of short induction on notation for nondeterministic polynomial-time computable relations, has the property that those functions having nondeterministic polynomial-time graph Θ such that TNC x y Θ are exactly the functions in NC, computable on a parallel random-access machine in polylogarithmic parallel time with a polynomial number of processors.0 We then define three theories of weak second-order arithmetic which respectively characterize relations in the classes of alternating logarithmic time, logspace and nondeterministic logspace

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

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

Through your library

Similar books and articles

The equivalence of theories that characterize ALogTime.Phuong Nguyen - 2009 - Archive for Mathematical Logic 48 (6):523-549.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
On interpretations of bounded arithmetic and bounded set theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Strict $${\Pi^1_1}$$ -reflection in bounded arithmetic.António M. Fernandes - 2010 - Archive for Mathematical Logic 49 (1):17-34.
An Independence Result on Weak Second Order Bounded Arithmetic.Satoru Kuroda - 2001 - Mathematical Logic Quarterly 47 (2):183-186.
Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.
Regularity in models of arithmetic.George Mills & Jeff Paris - 1984 - Journal of Symbolic Logic 49 (1):272-280.

Analytics

Added to PP
2014-01-16

Downloads
20 (#656,247)

6 months
3 (#445,838)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

On theories of bounded arithmetic for NC 1.Emil Jeřábek - 2011 - Annals of Pure and Applied Logic 162 (4):322-340.
Expander construction in VNC1.Sam Buss, Valentine Kabanets, Antonina Kolokolova & Michal Koucký - 2020 - Annals of Pure and Applied Logic 171 (7):102796.
A bounded arithmetic AID for Frege systems.Toshiyasu Arai - 2000 - Annals of Pure and Applied Logic 103 (1-3):155-199.
RSUV isomorphisms for TAC i , TNC i and TLS.G. Takeuti - 1995 - Archive for Mathematical Logic 33 (6):427-453.
A note on sharply bounded arithmetic.Jan Johannsen - 1994 - Archive for Mathematical Logic 33 (2):159-165.

View all 11 citations / Add more citations

References found in this work

Proof theory.Gaisi Takeuti - 1975 - New York, N.Y., U.S.A.: Sole distributors for the U.S.A. and Canada, Elsevier Science Pub. Co..
Subrecursion: functions and hierarchies.H. E. Rose - 1984 - New York: Oxford University Press.
On parameter free induction schemas.R. Kaye, J. Paris & C. Dimitracopoulos - 1988 - Journal of Symbolic Logic 53 (4):1082-1097.
Arithmetizing Uniform NC.Bill Allen - 1991 - Annals of Pure and Applied Logic 53 (1):1-50.

View all 7 references / Add more references