THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS

Autor:	Klaus-Jörn Lange, Pascal Tesson, Bernd Borchert, Denis Thérien, Frank Stephan
Rok vydání:	2005
Předmět:	Combinatorics Polynomial hierarchy Discrete mathematics Polynomial Hierarchy Conjecture Computer Science (miscellaneous) Upper and lower bounds Mathematics
Zdroj:	International Journal of Foundations of Computer Science. 16:625-644
ISSN:	1793-6373 0129-0541
DOI:	10.1142/s0129054105003200
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::6f1461f9f04cacb5553c9b2ed79a7c0e https://doi.org/10.1142/s0129054105003200 Zobrazit plný text záznamu