A Reducibility that Corresponds to Unbalanced Leaf-Language Classes
Christian Glaßer, Stephen D. Travers, Klaus W. Wagner · 2005
We introduce the polynomial-time tree reducibility (ptt-reducibility). Our main result states that for languages B and C it holds that B ptt-reduces to C if and only if the unbalanced leaf-language class of B is robustly contained in the unbalanced leaf-language class of C. This is the unbalanced analogue of the well-known result by Bovet, Crescenzi, Silvestri, and Vereshchagin which connects polylog-time reducibility with balanced leaf-languages. We show that restricted to regular languages, the levels 0, 1/2, 1, and 3/2 of the dot-depth hierarchy (DDH) are closed under ptt-reducibility. This gives evidence that with respect to unbalanced leaf-languages, the dot-depth hierarchy and the polynomial-time hierarchy perfectly correspond. Level 0 of the DDH is closed under ptt-reducibility even without the restriction to regular languages. We show that this does not hold for higher levels. As a consequence of our study of ptt-reducibility, we obtain the first gap theorem of leaf-language definability above the Boolean closure of NP: IfD =Leaf p u (C) for some C⊆REG, then D⊆ BC(NP) or there exists an oracle O such that DO NP[ɛ·log n]O � ⊆ P for every ɛ<1. 1