Annals of Pure and Applied Logic 104 (1-3):279-303 (2000)

We introduce multifunction algebras B i τ where τ is a set of 0 or 1-ary terms used to bound recursion lengths. We show that if for all ℓ ∈ τ we have ℓ ∈ O then B i τ = FP Σ i−1 p , those multifunctions computable in polynomial time with at most O )) queries to a Σ i−1 p witness oracle for ℓ ∈ τ and p a polynomial. We use our algebras to obtain independence results in bounded arithmetic. In particular, we show if S 2 i proves Σ j b = PH for some j⩾i then S 2 i ≼ B S 2 . This implies if P NP ≠ P NP then S 2 1 does not prove the polynomial hierarchy collapses. We then consider a subtheory, Z , of the well-studied bounded arithmetic theory S 2 = ∪ i S 2 i . Using our algebras we establish the following properties of this theory: Z cannot prove the polynomial hierarchy collapses. In fact, even Z+ Π ̂ 0 b -consequences of S 2 cannot prove the hierarchy collapses. If Z ⊆ S 2 i for any i then the polynomial hierarchy collapses. If Z proves the polynomial hierarchy is infinite then for all i , S 2 i ⊢ Σ i p ≠ Π i p
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(00)00015-4
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 72,541
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Existence and Feasibility in Arithmetic.Rohit Parikh - 1971 - Journal of Symbolic Logic 36 (3):494-508.
Structure and Definability in General Bounded Arithmetic Theories.Chris Pollett - 1999 - Annals of Pure and Applied Logic 100 (1-3):189-245.

View all 6 references / Add more references

Citations of this work BETA

A Theory for Log-Space and NLIN Versus Co-NLIN.Chris Pollett - 2003 - Journal of Symbolic Logic 68 (4):1082-1090.
On the Finite Axiomatizability of ∀Σ̂1b.Chris Pollett - 2018 - Mathematical Logic Quarterly 64 (1-2):6-24.

View all 9 citations / Add more citations

Similar books and articles

Provability Algebras and Proof-Theoretic Ordinals, I.Lev D. Beklemishev - 2004 - Annals of Pure and Applied Logic 128 (1-3):103-123.
Undecidability in Diagonalizable Algebras.V. Yu Shavrukov - 1997 - Journal of Symbolic Logic 62 (1):79-116.
On the Provability Logic of Bounded Arithmetic.Rineke Verbrugge & Alessandro Berarducci - 1991 - Annals of Pure and Applied Logic 61 (1-2):75-93.
Bounded BCK‐Algebras and Their Generated Variety.Joan Gispert & Antoni Torrens - 2007 - Mathematical Logic Quarterly 53 (2):206-213.
Free Łukasiewicz Implication Algebras.José Patricio Díaz Varela - 2008 - Archive for Mathematical Logic 47 (1):25-33.


Added to PP index

Total views
12 ( #815,687 of 2,533,478 )

Recent downloads (6 months)
1 ( #391,480 of 2,533,478 )

How can I increase my downloads?


My notes