ECCC-Report TR02-009https://eccc.weizmann.ac.il/report/2002/009Comments and Revisions published for TR02-009en-usMon, 21 Jan 2002 12:51:03 +0200
Paper TR02-009
| On determinism versus unambiquous nondeterminism for decision trees |
Petr Savicky
https://eccc.weizmann.ac.il/report/2002/009Let $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$.
Mon, 21 Jan 2002 12:51:03 +0200https://eccc.weizmann.ac.il/report/2002/009