<p>As pointed out by the OP (user13772), this is false.  Jukna et al. constructed explicit Boolean functions $f$ that require deterministic decision trees of size $2^{\Omega(\log^2 N)}$, where $N$ is the number of monomials in a minimal DNF for $f$ and $\lnot f$.  Note that every Boolean function on $n$ inputs can be expressed as a deterministic decision tree of size $2^{O(\log n \log^2 N)}$.</p>

<ul>
<li>S. Jukna, A. Razborov, P. Savický, I. Wegener, <em>On P versus NP$\cap$co-NP for decision trees and read-once branching programs</em>, Computational Complexity <strong>8</strong> (1999), 357–370.  doi:<a href="http://dx.doi.org/10.1007/s000370050005" rel="nofollow">10.1007/s000370050005</a>  (<a href="http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/ftp/dt.pdf" rel="nofollow">preprint</a>)</li>
</ul>

CC BY-SA 3.0
2013-05-18T21:05:58.193Z
2013-05-18T21:05:58.193Z
András Salamon
<p>Not sure what you mean by "number of leaves in a decision tree", as the decision tree is usually a full tree.
If you mean the number of nodes in a BDD (where you can essentially omit unnecessary tests), then I'm pretty sure you can construct a BDD that is at most the size of a DNF formula - simply test each clause "separately" (i.e. on a different branch), this can take at most the length of the DNF representation. </p>

CC BY-SA 3.0
2013-02-16T11:14:22.407Z
Actually, I just learned that this claim is false. Check:http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/ftp/dt.ps
user13772
CC BY-SA 3.0
2013-02-16T11:09:17.407Z
2013-02-16T11:09:17.407Z
Shaull
<p>I've been having hard time with proving the following claim:
Let $f:\{T,F\}^n\rightarrow \{T,F\}$ be a boolean function. Let $size_{DT}(f)$ denote the number of leaves in the smallest (w.r.t the number of leaves) decision tree for $f$. Also, let $size_{CNF}(f),size_{DNF}(f)$ denote the number of clauses, terms in the minimal $CNF,DNF$ formulas for $f$ respectively.</p>

<p>Prove that $size_{DT}(f)\in poly(n,size_{DNF}(f),size_{CNF}(f))$.</p>

CC BY-SA 3.0
2013-02-16T11:15:08.647Z
I just learned that this claim is incorrect, check:
http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/ftp/dt.ps
user13772
CC BY-SA 3.0
2013-03-18T16:54:15.773Z
It would be good to that as an answer and explain why it answers your question a bit more.
Kaveh
<cc.complexity-theory><machine-learning><boolean-functions><combinatory-logic><boolean-formulas>
Size of decision tree for f is polynomial in the DNF size of f and CNF size of f
user13772
# Size of decision tree for f is polynomial in the DNF size of f and CNF size of f

(Asked by: username_0 on 2013-02-16)

I've been having hard time with proving the following claim:
Let $f:\{T,F\}^n\rightarrow \{T,F\}$ be a boolean function. Let $size\_{DT}(f)$ denote the number of leaves in the smallest (w.r.t the number of leaves) decision tree for $f$. Also, let $size\_{CNF}(f),size\_{DNF}(f)$ denote the number of clauses, terms in the minimal $CNF,DNF$ formulas for $f$ respectively.

Prove that $size\_{DT}(f)\in poly(n,size\_{DNF}(f),size\_{CNF}(f))$.

**Tags:** cc.complexity-theory, machine-learning, boolean-functions, combinatory-logic, boolean-formulas
> **Comments:**
> **username_0**: I just learned that this claim is incorrect, check: http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/ftp/dt.ps  
> **username_1**: It would be good to that as an answer and explain why it answers your question a bit more.  

---

## 2 answers

### Answer by username_2 on 2013-05-18. Score: 4

As pointed out by the OP (user13772), this is false. Jukna et al. constructed explicit Boolean functions $f$ that require deterministic decision trees of size $2^{\Omega(\log^2 N)}$, where $N$ is the number of monomials in a minimal DNF for $f$ and $\lnot f$. Note that every Boolean function on $n$ inputs can be expressed as a deterministic decision tree of size $2^{O(\log n \log^2 N)}$.

* S. Jukna, A. Razborov, P. Savický, I. Wegener, *On P versus NP$\cap$co-NP for decision trees and read-once branching programs*, Computational Complexity **8** (1999), 357–370. doi:[10.1007/s000370050005](http://dx.doi.org/10.1007/s000370050005) ([preprint](http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/ftp/dt.pdf))


---

### Answer by username_3 on 2013-02-16. Score: 1

Not sure what you mean by "number of leaves in a decision tree", as the decision tree is usually a full tree.
If you mean the number of nodes in a BDD (where you can essentially omit unnecessary tests), then I'm pretty sure you can construct a BDD that is at most the size of a DNF formula - simply test each clause "separately" (i.e. on a different branch), this can take at most the length of the DNF representation.

> **Comments:**
> **username_0**: Actually, I just learned that this claim is false. Check:http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/ftp/dt.ps  

---

