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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,783

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

Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Review: Jan Krajicek, Pavel Pudlak, Gaisi Takeuti, Bounded Arithmetic and the Polynomial Hierarchy; Samuel R. Buss, Relating the Bounded Arithmetic and Polynomial Time Hierarchies; Domenico Zambella, Notes on Polynomially Bounded Arithmetic. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.
Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
An Independence Result on Weak Second Order Bounded Arithmetic.Satoru Kuroda - 2001 - Mathematical Logic Quarterly 47 (2):183-186.
Relating the bounded arithmetic and polynomial time hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
The strength of sharply bounded induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.
An unexpected separation result in Linearly Bounded Arithmetic.Arnold Beckmann & Jan Johannsen - 2005 - Mathematical Logic Quarterly 51 (2):191-200.
Polynomial induction and length minimization in intuitionistic bounded arithmetic.Morteza Moniri - 2005 - Mathematical Logic Quarterly 51 (1):73-76.
The polynomial and linear time hierarchies in V0.Leszek A. Kołodziejczyk & Neil Thapen - 2009 - Mathematical Logic Quarterly 55 (5):509-514.
A Remark on Independence Results for Sharply Bounded Arithmetic.Jan Johannsen - 1998 - Mathematical Logic Quarterly 44 (4):568-570.
Preservation theorems for bounded formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
Two General Results on Intuitionistic Bounded Theories.Fernando Ferreira - 1999 - Mathematical Logic Quarterly 45 (3):399-407.
Finite reverse mathematics.Harvey Friedman - manuscript
On interpretations of bounded arithmetic and bounded set theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.

Analytics

Added to PP
2017-02-21

Downloads
7 (#1,384,540)

6 months
1 (#1,467,486)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
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.
Saturated models of universal theories.Jeremy Avigad - 2002 - Annals of Pure and Applied Logic 118 (3):219-234.
Elementary analytic functions in VT C 0.Emil Jeřábek - 2023 - Annals of Pure and Applied Logic 174 (6):103269.

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