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

<p>There is a chapter in <a href="http://books.google.de/books?id=wu6HG2w_FQ8C&amp;lpg=PP1&amp;pg=PP1#v=onepage&amp;q&amp;f=false" rel="nofollow" title="Branching programs and binary decision diagrams: theory and applications">Branching programs and binary decision diagrams: theory and applications</a> by Ingo Wegener about the size of decision trees for boolean functions. </p>

<p>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.</p>

<p>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))}. $$</p>

CC BY-SA 3.0
2015-09-04T14:53:41.293Z
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.
Marc
CC BY-SA 4.0
2021-09-17T04:39:28.240Z
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)?
Clay Thomas
CC BY-SA 3.0
2011-06-07T10:10:38.977Z
2011-06-07T10:10:38.977Z
Marc Bury
<p>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$?</p>

<p>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).</p>

CC BY-SA 3.0
2011-06-07T01:39:46.677Z
A related concept will be the [decision tree complexity](http://en.wikipedia.org/wiki/Decision_tree_complexity). But instead of using size as a measure, it uses the depth of the decision tree.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-06-07T05:30:26.327Z
I'm more interested in the size though. Another way of stating my questions would be to ask if you consider $f$ and $m$, are there bounds in $m$ on the smallest DT-DNF (or DT-CNF), that is, Decision Tree DNF?
MGwynne
<cc.complexity-theory><sat><boolean-functions><binary-decision-diagrams><decision-trees>
Bounds on the size of smallest decision tree for a boolean function?
MGwynne
# Bounds on the size of smallest decision tree for a boolean function?

(Asked by: username_0 on 2011-06-06)

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).

**Tags:** cc.complexity-theory, sat, boolean-functions, binary-decision-diagrams, decision-trees

> **Comments:**
> **username_1**: A related concept will be the [decision tree complexity](http://en.wikipedia.org/wiki/Decision_tree_complexity). But instead of using size as a measure, it uses the depth of the decision tree.  
> **username_0**: I'm more interested in the size though. Another way of stating my questions would be to ask if you consider $f$ and $m$, are there bounds in $m$ on the smallest DT-DNF (or DT-CNF), that is, Decision Tree DNF?  

---

## 1 answers

### Answer by username_2 on 2011-06-07. Score: 7 | Accepted answer

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](http://books.google.de/books?id=wu6HG2w_FQ8C&lpg=PP1&pg=PP1#v=onepage&q&f=false "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:**
> **username_3**: 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.  
> **username_4**: 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)?  

---

