Relating the bounded arithmetic and polynomial time hierarchies

Annals of Pure and Applied Logic 75 (1-2):67-77 (1995)
  Copy   BIBTEX

Abstract

The bounded arithmetic theory S2 is finitely axiomatized if and only if the polynomial hierarchy provably collapses. If T2i equals S2i + 1 then T2i is equal to S2 and proves that the polynomial time hierarchy collapses to ∑i + 3p, and, in fact, to the Boolean hierarchy over ∑i + 2p and to ∑i + 1p/poly

Categories

Keywords

Reprint years

DOI

10.1016/0168-0072(94)00057-a

Other Versions

No versions found

Links

PhilArchive



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

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.
Multifunction algebras and the provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
The polynomial and linear time hierarchies in V0.Leszek A. Kołodziejczyk & Neil Thapen - 2009 - Mathematical Logic Quarterly 55 (5):509-514.
Polynomial induction and length minimization in intuitionistic bounded arithmetic.Morteza Moniri - 2005 - Mathematical Logic Quarterly 51 (1):73-76.
Consequences of the Provability of NP ⊆ P/poly.Stephen Cook & Jan Krajíček - 2007 - Journal of Symbolic Logic 72 (4):1353 - 1371.
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.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
On parallel hierarchies and Rki.Stephen Bloch - 1997 - Annals of Pure and Applied Logic 89 (2-3):231-273.

Analytics

Added to PP
2014-01-16

Downloads
25 (#877,287)

6 months
6 (#851,951)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The strength of sharply bounded induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.
Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
End extensions of models of linearly bounded arithmetic.Domenico Zambella - 1997 - Annals of Pure and Applied Logic 88 (2-3):263-277.
A model-theoretic characterization of the weak pigeonhole principle.Neil Thapen - 2002 - Annals of Pure and Applied Logic 118 (1-2):175-195.

View all 19 citations / Add more citations

References found in this work

On the scheme of induction for bounded arithmetic formulas.A. J. Wilkie & J. B. Paris - 1987 - Annals of Pure and Applied Logic 35 (C):261-302.
Existence and feasibility in arithmetic.Rohit Parikh - 1971 - Journal of Symbolic Logic 36 (3):494-508.
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.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.

Add more references