Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR02-009 | 17th January 2002 00:00

#### On determinism versus unambiquous nondeterminism for decision trees

TR02-009
Authors: Petr Savicky
Publication: 21st January 2002 12:51
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