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

Categories

Keywords

Reprint years

DOI

10.2307/2275794

Other Versions

No versions found

Links

PhilArchive

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

Jan Krajíček, Pavel Pudlák, and Gaisi Takeuti. Bounded arithmetic and the polynomial hierarchy. Ibid., vol. 52, pp. 143–153. - Samuel R. Buss. Relating the bounded arithmetic and polynomial time hierarchies. Ibid., vol. 75, pp. 67–77. - Domenico Zambella. Notes on polynomially bounded arithmetic. The journal of symbolic logic, vol. 61, pp. 942–966.Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
The polynomial and linear time hierarchies in V0.Leszek A. Kołodziejczyk & Neil Thapen - 2009 - Mathematical Logic Quarterly 55 (5):509-514.
Preservation theorems for bounded formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
A Counterexample to Polynomially Bounded Realizability of Basic Arithmetic.Mohammad Ardeshir, Erfan Khaniki & Mohsen Shahriari - 2019 - Notre Dame Journal of Formal Logic 60 (3):481-489.
Unprovability of consistency statements in fragments of bounded arithmetic.Samuel R. Buss & Aleksandar Ignjatović - 1995 - Annals of Pure and Applied Logic 74 (3):221-244.
Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.
Separations of first and second order theories in bounded arithmetic.Masahiro Yasumoto - 2005 - Archive for Mathematical Logic 44 (6):685-688.
The strength of sharply bounded induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.
A Model‐Theoretic Property of Sharply Bounded Formulae, with some Applications.Jan Johannsen - 1998 - Mathematical Logic Quarterly 44 (2):205-215.

Analytics

Added to PP
2009-01-28

Downloads
223 (#181,754)

6 months
42 (#200,999)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Strict Finitism, Feasibility, and the Sorites.Walter Dean - 2018 - Review of Symbolic Logic 11 (2):295-346.
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.
Another look at the second incompleteness theorem.Albert Visser - 2020 - Review of Symbolic Logic 13 (2):269-295.
Relating the bounded arithmetic and polynomial time hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.

View all 40 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.

Add more references