THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
- 1 August 2005
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 16 (04) , 625-644
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: [Formula: see text]. 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.Keywords
This publication has 16 references indexed in Scilit:
- Randomness is HardSIAM Journal on Computing, 2000
- On Existentially First-Order Definable Languages and Their Relation to NPRAIRO - Theoretical Informatics and Applications, 1999
- LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITYInternational Journal of Foundations of Computer Science, 1998
- A characterization of the leaf language classesInformation Processing Letters, 1997
- A uniform approach to define complexity classesTheoretical Computer Science, 1992
- Bounded Query ClassesSIAM Journal on Computing, 1990
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy CollapsesSIAM Journal on Computing, 1988
- Locally trivial categories and unambiguous concatenationJournal of Pure and Applied Algebra, 1988
- Relativized polynomial hierarchies extending two levelsTheory of Computing Systems, 1984
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975