Loading jsMath...
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: 2975
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