TR05-035 Authors: Christian Glaßer, Stephen Travers, Klaus W. Wagner

Publication: 8th April 2005 19:13

Downloads: 2377

Keywords:

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$.