Abstract

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