Partial collapses of the complexity hierarchy in models for fragments of bounded arithmetic

&
Annals of Pure and Applied Logic 145 (1):91-95 (2007)
  Copy   BIBTEX

Abstract

For any n, we construct a model of in which each formula is equivalent to an formula

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2006.06.002

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,561

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

Relating the bounded arithmetic and polynomial time hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
Arithmetizing Uniform NC.Bill Allen - 1991 - Annals of Pure and Applied Logic 53 (1):1-50.
Expressive equivalence of least and inflationary fixed-point logic.Stephan Kreutzer - 2004 - Annals of Pure and Applied Logic 130 (1-3):61-78.
Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic.Arnold Beckmann & Samuel R. Buss - 2009 - Journal of Mathematical Logic 9 (1):103-138.
Existentially Closed Models in the Framework of Arithmetic.Zofia Adamowicz, Andrés Cordón-Franco & F. Félix Lara-martín - 2016 - Journal of Symbolic Logic 81 (2):774-788.
A Model‐Theoretic Property of Sharply Bounded Formulae, with some Applications.Jan Johannsen - 1998 - Mathematical Logic Quarterly 44 (2):205-215.
A model-theoretic characterization of the weak pigeonhole principle.Neil Thapen - 2002 - Annals of Pure and Applied Logic 118 (1-2):175-195.
Quantifier elimination for modules with scalar variables.Lou van den Dries & Jan Holly - 1992 - Annals of Pure and Applied Logic 57 (2):161-179.
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.
A nonasymptotic lower time bound for a strictly bounded second-order arithmetic.Anatoly P. Beltiukov - 2006 - Annals of Pure and Applied Logic 141 (3):320-324.

Analytics

Added to PP
2013-12-30

Downloads
36 (#606,239)

6 months
3 (#1,467,341)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

Cuts, consistency statements and interpretations.Pavel Pudlák - 1985 - Journal of Symbolic Logic 50 (2):423-441.
On Maximal Theories.Zofia Adamowicz - 1991 - Journal of Symbolic Logic 56 (3):885-890.

Add more references