Abstract:
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 {\em unbalanced} analogue of the well-known result by Bovet, Crescenzi, Silvestri, and Vereshchagin which connects polylog-time reducibility with {\em 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 $\cNP$: If ${\cal D} = \ULeaf({\cal C})$ for some ${\cal C} \subseteq \REG$, then ${\cal D} \subseteq \bc(\cNP)$ or there exists an oracle $O$ such that ${\cal D}^O \not\subseteq \cP^{\cNP[\epsilon \cdot \log n]^O}$ for every $\epsilon < 1$.