ECCC-Report TR05-035https://eccc.weizmann.ac.il/report/2005/035Comments and Revisions published for TR05-035en-usFri, 08 Apr 2005 19:13:09 +0300
Paper TR05-035
| A Reducibility that Corresponds to Unbalanced Leaf-Language Classes |
Christian Glaßer,
Stephen Travers,
Klaus W. Wagner
https://eccc.weizmann.ac.il/report/2005/035We 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$.
Fri, 08 Apr 2005 19:13:09 +0300https://eccc.weizmann.ac.il/report/2005/035