Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-035 | 24th March 2005 00:00

A Reducibility that Corresponds to Unbalanced Leaf-Language Classes



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

ISSN 1433-8092 | Imprint