Journal of Symbolic Logic 61 (3):942-966 (1996)

Abstract
We characterize the collapse of Buss' bounded arithmetic in terms of the provable collapse of the polynomial time hierarchy. We include also some general model-theoretical investigations on fragments of bounded arithmetic
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2275794
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: 63,110
Through your library

References found in this work BETA

Bounded Arithmetic and the Polynomial Hierarchy.Jan Krajíček, Pavel Pudlák & Gaisi Takeuti - 1991 - Annals of Pure and Applied Logic 52 (1-2):143-153.
¹1-Formulae on Finite Structures.M. Ajtai - 1983 - Annals of Pure and Applied Logic 24 (1):1.
Exponentiation and Second-Order Bounded Arithmetic.Jan Krajíček - 1990 - Annals of Pure and Applied Logic 48 (3):261-276.
Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (2):942-966.

Add more references

Citations of this work BETA

Another Look at the Second Incompleteness Theorem.Albert Visser - 2020 - Review of Symbolic Logic 13 (2):269-295.
Growing Commas. A Study of Sequentiality and Concatenation.Albert Visser - 2009 - Notre Dame Journal of Formal Logic 50 (1):61-85.
Saturated Models of Universal Theories.Jeremy Avigad - 2002 - Annals of Pure and Applied Logic 118 (3):219-234.
Relating the Bounded Arithmetic and Polynomial Time Hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
On Theories of Bounded Arithmetic for NC 1.Emil Jeřábek - 2011 - Annals of Pure and Applied Logic 162 (4):322-340.

View all 32 citations / Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
47 ( #226,733 of 2,448,086 )

Recent downloads (6 months)
1 ( #451,143 of 2,448,086 )

How can I increase my downloads?

Downloads

My notes