Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-009 | 17th January 2002 00:00

On determinism versus unambiquous nondeterminism for decision trees

RSS-Feed




TR02-009
Authors: Petr Savicky
Publication: 21st January 2002 12:51
Downloads: 2894
Keywords: 


Abstract:

Let $f$ be a Boolean function. Let $N(f)=\dnf(f)+\dnf(\neg f)$ be the
sum of the minimum number of monomials in a disjunctive normal form
for $f$ and $\neg f$. Let $p(f)$ be the minimum size of a partition
of the Boolean cube into disjoint subcubes such that $f$ is constant on
each of the subcubes. Let $\dt(f)$ be the minimum size (number of leaves)
of a decision tree for $f$. Clearly, $\dt(f) \ge p(f) \ge N(f)$.
It is known that $\dt(f)$ can be at most quasipolynomially larger than
$N(f)$ and a quasipolynomial separation between $p(f)$ and $N(f)$
for a sequence of functions $f$ is known. We present a quasipolynomial
separation between $\dt(f)$ and $p(f)$ for another sequence of functions $f$.



ISSN 1433-8092 | Imprint