Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > POLYLOG-TIME REDUCIBILITY:
Reports tagged with polylog-time reducibility:
TR05-035 | 24th March 2005
Christian Glaßer, Stephen Travers, Klaus W. Wagner

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




ISSN 1433-8092 | Imprint