Archive for Mathematical Logic 48 (6):523-549 (2009)

Authors
Phuong Nguyen
University of Georgia
Abstract
A number of theories have been developed to characterize ALogTime (or uniform NC 1, or just NC 1), the class of languages accepted by alternating logtime Turing machines, in the same way that Buss’s theory ${{\bf S}^{1}_{2}}$ characterizes polytime functions. Among these, ALV′ (by Clote) is particularly interesting because it is developed based on Barrington’s theorem that the word problem for the permutation group S 5 is complete for ALogTime. On the other hand, ALV (by Clote), T 0 NC 0 (by Clote and Takeuti) as well as Arai’s theory ${{\bf AID}+\Sigma_0^B{-}{\bf CA}}$ and its two-sorted version VNC 1 (by Cook and Morioka) are based on the circuit characterization of ALogTime. While the last three theories have been known to be equivalent, their relationship to ALV′ has been an open problem. Here we show that ALV′ is indeed equivalent to the other theories
Keywords Bounded arithmetic  ALogTime  Complexity theory
Categories (categorize this paper)
DOI 10.1007/s00153-009-0136-4
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 53,047
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

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.
Exponentiation and Second-Order Bounded Arithmetic.Jan Krajíček - 1990 - Annals of Pure and Applied Logic 48 (3):261-276.
A Bounded Arithmetic AID for Frege Systems.Toshiyasu Arai - 2000 - Annals of Pure and Applied Logic 103 (1-3):155-199.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Bounded Arithmetic for NC, ALogTIME, L and NL.P. Clote & G. Takeuti - 1992 - Annals of Pure and Applied Logic 56 (1-3):73-117.
On Interpretations of Bounded Arithmetic and Bounded Set Theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Interpreting Classical Theories in Constructive Ones.Jeremy Avigad - 2000 - Journal of Symbolic Logic 65 (4):1785-1812.
Preservation Theorems for Bounded Formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
Dynamic Ordinal Analysis.Arnold Beckmann - 2003 - Archive for Mathematical Logic 42 (4):303-334.
Generalized Quantifier and a Bounded Arithmetic Theory for LOGCFL.Satoru Kuroda - 2007 - Archive for Mathematical Logic 46 (5-6):489-516.
Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.

Analytics

Added to PP index
2013-11-23

Total views
71 ( #132,791 of 2,344,275 )

Recent downloads (6 months)
17 ( #38,143 of 2,344,275 )

How can I increase my downloads?

Downloads

My notes