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



    Upload a copy of this work     Papers currently archived: 97,297

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. [REVIEW]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.

Analytics

Added to PP
2009-01-28

Downloads
87 (#202,441)

6 months
28 (#134,878)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Iterated multiplication in $$ VTC ^0$$ V T C 0.Emil Jeřábek - 2022 - Archive for Mathematical Logic 61 (5):705-767.
Iterated multiplication in $$ VTC ^0$$.Emil Jeřábek - 2022 - Archive for Mathematical Logic 61 (5):705-767.
Strict Finitism, Feasibility, and the Sorites.Walter Dean - 2018 - Review of Symbolic Logic 11 (2):295-346.
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.

View all 38 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