A binary decision tree $T$ is a rooted tree where each internal node (and root) is labeled by an index $j \in \{1,..., n\}$ such that no path from root to leaf repeats an index, the leafs are labeled by outputs in $\{A,B\}$, and each edge is labeled by $0$ for the left child and $1$ for the right child. To apply a tree to an input $x$:

  1. Start at the root
  2. if you are at leaf, you output the leaf label $A$ or $B$ and terminate
  3. Read the label $j$ of your current node, if $x_j = 0$ then move to the left child and if $x_j = 1$ then move to the right child.
  4. jump to step (2)

The tree is used as a way to evaluate a functions, in particular we say a tree $T$ represents a total function $f$ if for each $x \in \{0,1\}^n$ we have $T(x) = f(x)$. The query complexity of a tree is its depth, and the query complexity of a function is the depth of the smallest tree that represents it.


Given a binary decision tree T output a binary decision tree T' of minimal depth such that T and T' represent the same function.


What is the best known algorithm for this? Are any lower bounds known? What if we know that the $\text{depth}(T') = O(\log \text{depth}(T))$? What about if we only require $T'$ to be of approximately minimal depth?

Naive approach

The naive approach is given $d = \text{depth}(T)$ to recursively enumerate all binary decision trees of depth $d - 1$ while testing if they evaluate to the same thing as $T$. This seems to require $O(\frac{d 2^n n!}{(n - d)!})$ steps (assuming that it takes $d$ steps to check what $T(x)$ evaluates to for an arbitrary $x$). Is there a better approach?


This question is motivated by a previous question on the trade off between query complexity and time complexity. In particular, the goal is to bound the time separation for total functions. We can make a tree $T$ from a time optimal algorithm with runtime $t$, and then we would like to convert it to a tree $T'$ for a query optimal algorithm. Unfortunately, if $t \in O(n!/(n - d)!)$ (and often $d \in \Theta(n)$) the bottleneck is the conversion. It would be nice if we could replace $n!/(n - d)!$ by something like $2^d$.

  • $\begingroup$ Finding the optimal decision tree is NP-complete. I was taught that in Decision theory and Data mining classes, however those were based on notes and I am not aware of the original paper that introduced the result. $\endgroup$
    – chazisop
    Commented Jul 31, 2011 at 13:09
  • 1
    $\begingroup$ @chazisop cool, thanks. It is not obvious to me that finding the optimal decision tree is in NP, but I will think about it/search for it some more. Sometimes knowing the theorem statement is halfway to proving it :D. $\endgroup$ Commented Jul 31, 2011 at 16:42
  • $\begingroup$ I think the earliest reference for this is: Lower Bounds on Learning Decision Lists and Trees. (Hancock et al. 1994) cs.uwaterloo.ca/~mli/dl.ps $\endgroup$
    – Lev Reyzin
    Commented Aug 25, 2011 at 1:37
  • 1
    $\begingroup$ The proof that finding the optimal decision tree is a NP-complete problem was given by Laurent Hyafil and Ronald L. Rivest in Constructing optimal binary decision trees is NP-complete (1976). reference: here $\endgroup$
    – antoine
    Commented Nov 5, 2013 at 20:47

1 Answer 1


I have 3 answers, all giving somewhat different hardness results.

Let $f: \{0,1\}^n \rightarrow \{0,1\}$ be some function.

Answer 1

Given a decision tree $T$ computing $f$ and a number, it is NP-hard to tell if there exists a decision tree $T'$ computing $f$ of size at most that number. (Zantema and Bodlaender '00)

Answer 2

Given a decision tree $T$ computing $f$, it is NP hard to approximate the smallest decision tree computing $f$ to any constant factor. (Sieling '08)

Answer 3

Let $s$ be the size of the smallest decision tree computing $f$. Given a decision tree $T$ computing $f$, assuming $NP \subsetneq DTIME(2^{n^\epsilon})$ for some $\epsilon < 1$, one cannot find an equivalent decision tree $T'$ of size $s^k$ for any $k \ge 0$.

I think that this stronger answer (relying on a weaker assumption) can be made from known results in the learning theory of Occam algorithms for decision trees, via the following argument:

  1. Is it possible to find a decision tree on $n$ variables in time $n^{\log s}$, where $s$ is the smallest decision tree consistent with examples coming from a distribution (PAC model). (Blum '92)
  2. Assuming $NP \subsetneq DTIME(2^{n^\epsilon})$ for some $\epsilon < 1$, we cannot PAC learn size $s$ decision trees by size $s^k$ decision trees for any $k \ge 0$. (Alekhnovich et al. '07)

These two results seem to imply a hardness result for your problem. On the one hand (1), we can find a large decision tree; on the other hand (2), we shouldn't be able to minimize it to get an equivalent "small" one, of size $s^k$, even when one exists of size $s$.

  • $\begingroup$ (I found your answer from this answer, which was posted less than an hour ago.) $\:$ It looks like "$\epsilon < 1$" can be replaced with "positive $\epsilon$, since decreasing $\epsilon$ makes the containment's right-hand-side smaller. $\:$ Also, where in that paper is 2. shown? $\;\;\;\;$ $\endgroup$
    – user6973
    Commented Jul 7, 2015 at 0:51
  • $\begingroup$ See bullet point #2 in the abstract here: researcher.watson.ibm.com/researcher/files/us-vitaly/… $\endgroup$
    – Lev Reyzin
    Commented Jul 7, 2015 at 11:46
  • $\begingroup$ (coming from the same answer as Ricky Demer) could you detail a bit more how do you get "answer 3" from points 1. and 2.? I am not very familiar with learning theory and have a hard time connecting the parts... $\endgroup$
    – Marc
    Commented Jul 8, 2015 at 17:03
  • $\begingroup$ This consistency problem and learnability are closely related via Occam's razor. The idea is that if you can find a consistent function from a small set, you can succeed in PAC learning. Therefore a hardness of learning result implies a "hardness of consistency" result. I'm not sure how much more I can explain in a comment... $\endgroup$
    – Lev Reyzin
    Commented Jul 8, 2015 at 18:24
  • 2
    $\begingroup$ It seems that all results commented here concern minimizing the size of the decision tree (number of nodes or number of leaves), but the original question concerns minimizing its depth. Is there any result for the depth? $\endgroup$ Commented Nov 13, 2017 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.