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

doi:10.1142/S0129054105003200

beta

Join waitlist

Finding

The same methods are used to give evidence against an earlier conjecture of Straubing and Therien about a leaf-language upper bound for BPP.

Paper

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

Citations: 4

2005

Full text

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: . The same methods are used to give evidence against an earlier conjecture of Straubing and Therien about a leaf-language upper bound for BPP.

Authors

Bernd Borchert, Klaus-Jörn Lange, F. Stephan

Journal

Int. J. Found. Comput. Sci.

copied to clipboard