Notes on polynomially bounded arithmetic

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

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

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

Analytics

Added to PP
2009-01-28

Downloads
55 (#259,880)

6 months
5 (#247,092)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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.
Strict finitism, feasibility, and the sorites.Walter Dean - 2018 - Review of Symbolic Logic 11 (2):295-346.
Iterated multiplication in $$ VTC ^0$$.Emil Jeřábek - forthcoming - Archive for Mathematical Logic.
Saturated models of universal theories.Jeremy Avigad - 2002 - Annals of Pure and Applied Logic 118 (3):219-234.

View all 36 citations / Add more citations

References found in this work

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.
Exponentiation and second-order bounded arithmetic.Jan Krajíček - 1990 - Annals of Pure and Applied Logic 48 (3):261-276.
¹1-formulae on finite structures.M. Ajtai - 1983 - Annals of Pure and Applied Logic 24 (1):1.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.

Add more references