Theoretical Computer Science
cc.complexity-theory sat boolean-functions binary-decision-diagrams decision-trees
Updated Wed, 15 Jun 2022 13:46:05 GMT

Bounds on the size of smallest decision tree for a boolean function?


Consider a boolean function $f : V \rightarrow \{0,1\}$ with $m$ true points. Are there any non-trivial bounds in $m$ on the size of the smallest decision tree for $f$?

It seems to me that assuming $f$ has $n$ variables and $m$ true points then any minimal decision tree has at most $$ 2^{\lceil{\log_2 m}\rceil}m+m(n\lceil{\log_2 m}\rceil) $$ 0-leaves (obviously, one can take the dual as well). I am wondering if whether this sort of thing has been covered before (I presume it has somewhere).

Solution

I think the number of true points isn't a good measure to say anything about the size of the smallest decision tree.

There is a chapter in Branching programs and binary decision diagrams: theory and applications by Ingo Wegener about the size of decision trees for boolean functions.

The size of the smallest DT is determined up to constant factors by the number of leaves of the tree. There is a lemma in the book that says: If you have a DT for a function $f$ with $s_0$ 0-leaves and $s_1$ 1-leaves then $f$ can be represented by a DNF with $s_1$ monomials and a CNF with $s_0$ clauses. So even if you have a function with only a small number of true points, the size of the smallest DT could be very large. So you need small size of CNF and DNF to have a small DT size.

There is a upper bound of the DT size with respect to the sum of the minimal number of monomials of $f$ and the minimal number of monomials of $\overline{f}$. Lets call this sum $DCNF(f)$. Then you have the following upper bound for the number of leaves $DT(f)$ of the smallest DT for the function $f: \lbrace 0,1 \rbrace^n \rightarrow \lbrace 0,1 \rbrace$ $$ DT(f) \leq n^{O(log^2 DCNF(f))}. $$

Comments (2)

  • +0 – If you are interested in lower bounds: later on in the same chapter of the same book, lower bounds on $DT(f)$ are obtained via Fourrier coefficients. — Sep 04, 2015 at 14:53  
  • +0 – Sorry, quick question: what is a "monomial" in this context? Is it a clause of a DNF (i.e. we treat + as OR and we treat * as AND)? And thus, is $DCNF(f)$ exactly the sum lower bounding the decision tree size (as in the prior paragraph)? — Sep 17, 2021 at 04:39  

External Links

External links referenced by this document:

References