The dot-depth and the polynomial hierarchies correspond on the delta levels

Abstract

It is well-known that the ∑ k- and Π k-levels of the dot-depth hierarchy and the polynomial hierarchy correspond via leaf languages. We extend this correspondence to the Δ k-levels of these hierarchies: Leaf P(Δ k L) = Δ k P. The same methods are used to give evidence against an earlier conjecture of Straubing and Thérien about a leaf-language upper bound for BPP. © World Scientific Publishing Company.