__
TR02-009 | 17th January 2002 00:00
__

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

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