<p>I have 3 answers, all giving somewhat different hardness results.</p>

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

<p><strong>Answer 1</strong></p>

<p><em>Given a decision tree $T$ computing $f$ and a number, it is NP-hard to tell if there exists a decision tree $T&#39;$ computing $f$ of size at most that number.</em> (<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.18.9838&amp;rep=rep1&amp;type=pdf">Zantema and Bodlaender '00</a>)</p>

<p><strong>Answer 2</strong></p>

<p><em>Given a decision tree $T$ computing $f$, it is NP hard to approximate the smallest decision tree computing $f$ to any constant factor.</em> (<a href="http://www.sciencedirect.com/science/article/pii/S0022000007000815">Sieling '08</a>)</p>

<p><strong>Answer 3</strong></p>

<p><em>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 &lt; 1$, one cannot find an equivalent decision tree $T&#39;$ of size $s^k$ for any $k \ge 0$.</em></p>

<p>I think that this stronger answer (relying on a weaker assumption) can be made from known results in the learning theory of <a href="http://blog.computationalcomplexity.org/2002/12/learning-via-occams-razor.html">Occam algorithms</a> for decision trees, via the following argument:  </p>

<ol>
<li>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). (<a href="http://www.sciencedirect.com/science/article/pii/002001909290237P">Blum '92</a>)  </li>
<li>Assuming $NP \subsetneq DTIME(2^{n^\epsilon})$ for some $\epsilon &lt; 1$, we cannot PAC learn size $s$ decision trees by size $s^k$ decision trees for any $k \ge 0$. (<a href="http://www.almaden.ibm.com/cs/people/vitaly/papers/ABFKP_Proper_Hardness_08.pdf">Alekhnovich et al. '07</a>)</li>
</ol>

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

CC BY-SA 3.0
2015-07-08T17:03:42.033Z
(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...
Marc
CC BY-SA 3.0
2015-07-08T18:24:44.523Z
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...
Lev Reyzin
CC BY-SA 3.0
2015-07-10T09:09:22.033Z
As far as I understand it, the algorithm evoked for 1. does not run in time $Poly(n,s)$ which would be necessary to get a contradiction with 2. (the precise result in the article if I got it correctly says that there is no polytime learning algorithm for decision trees). So there might be a problem with your argumentation.
Marc
CC BY-SA 3.0
2015-07-07T11:46:25.723Z
See bullet point #2 in the abstract here: http://researcher.watson.ibm.com/researcher/files/us-vitaly/ABFKP_Proper_Hardness_08.pdf
Lev Reyzin
CC BY-SA 3.0
2017-11-13T09:26:40.390Z
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?
EXPTIME-complete
CC BY-SA 3.0
2011-08-25T00:11:57.757Z
2011-08-25T00:11:57.757Z
Lev Reyzin
<h3>Background</h3>
<p>A binary decision tree <span class="math-container">$T$</span> is a rooted tree where each internal node (and root) is labeled by an index <span class="math-container">$j \in \{1,..., n\}$</span> such that no path from root to leaf repeats an index, the leafs are labeled by outputs in <span class="math-container">$\{A,B\}$</span>, and each edge is labeled by <span class="math-container">$0$</span> for the left child and <span class="math-container">$1$</span> for the right child. To apply a tree to an input <span class="math-container">$x$</span>:</p>
<ol>
<li>Start at the root</li>
<li>if you are at leaf, you output the leaf label <span class="math-container">$A$</span> or <span class="math-container">$B$</span> and terminate</li>
<li>Read the label <span class="math-container">$j$</span> of your current node, if <span class="math-container">$x_j = 0$</span> then move to the left child and if <span class="math-container">$x_j = 1$</span> then move to the right child.</li>
<li>jump to step (2)</li>
</ol>
<p>The tree is used as a way to evaluate a functions, in particular we say a tree <span class="math-container">$T$</span> represents a total function <span class="math-container">$f$</span> if for each <span class="math-container">$x \in \{0,1\}^n$</span> we have <span class="math-container">$T(x) = f(x)$</span>. 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.</p>
<hr />
<h3>Problem</h3>
<p>Given a binary decision tree T output a binary decision tree T' of minimal depth such that T and T' represent the same function.</p>
<h3>Question</h3>
<p>What is the best known algorithm for this? Are any lower bounds known? What if we know that the <span class="math-container">$\text{depth}(T') = O(\log \text{depth}(T))$</span>? What about if we only require <span class="math-container">$T'$</span> to be of approximately minimal depth?</p>
<hr />
<h3>Naive approach</h3>
<p>The naive approach is given <span class="math-container">$d = \text{depth}(T)$</span> to recursively enumerate all binary decision trees of depth <span class="math-container">$d - 1$</span> while testing if they evaluate to the same thing as <span class="math-container">$T$</span>. This seems to require <span class="math-container">$O(\frac{d 2^n n!}{(n - d)!})$</span> steps (assuming that it takes <span class="math-container">$d$</span> steps to check what <span class="math-container">$T(x)$</span> evaluates to for an arbitrary <span class="math-container">$x$</span>). Is there a better approach?</p>
<h3>Motivation</h3>
<p>This question is motivated by a previous question on the <a href="https://cstheory.stackexchange.com/q/7413/1037">trade off between query complexity and time complexity</a>. In particular, the goal is to bound the time separation for total functions. We can make a tree <span class="math-container">$T$</span> from a time optimal algorithm with runtime <span class="math-container">$t$</span>, and then we would like to convert it to a tree <span class="math-container">$T'$</span> for a query optimal algorithm. Unfortunately, if <span class="math-container">$t \in O(n!/(n - d)!)$</span> (and often <span class="math-container">$d \in \Theta(n)$</span>) the bottleneck is the conversion. It would be nice if we could replace <span class="math-container">$n!/(n - d)!$</span> by something like <span class="math-container">$2^d$</span>.</p>

CC BY-SA 3.0
2011-07-31T13:09:07.543Z
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.
chazisop
CC BY-SA 3.0
2011-07-31T16:42:36.137Z
@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.
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-25T01:37:39.910Z
I think the earliest reference for this is: Lower Bounds on Learning Decision Lists and Trees. (Hancock et al. 1994) http://www.cs.uwaterloo.ca/~mli/dl.ps
Lev Reyzin
CC BY-SA 3.0
2013-11-05T20:47:30.290Z
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](http://people.csail.mit.edu/rivest/HyafilRivest-ConstructingOptimalBinaryDecisionTreesIsNPComplete.pdf) (1976). reference: [here](http://www.cbcb.umd.edu/~salzberg/docs/murthy_thesis/survey/node27.html)
antoine
<ds.algorithms><query-complexity><decision-trees>
Algorithm for optimizing decision trees
Artem Kaznatcheev
# Algorithm for optimizing decision trees

(Asked by: username_0 on 2011-07-30)

### Background

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.

---

### Problem

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

### Question

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?

### Motivation

This question is motivated by a previous question on the [trade off between query complexity and time complexity](https://cstheory.stackexchange.com/q/7413/1037). 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$.

**Tags:** ds.algorithms, query-complexity, decision-trees

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 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.  
> **username_2**: I think the earliest reference for this is: Lower Bounds on Learning Decision Lists and Trees. (Hancock et al. 1994) http://www.cs.uwaterloo.ca/~mli/dl.ps  
> **username_3**: 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](http://people.csail.mit.edu/rivest/HyafilRivest-ConstructingOptimalBinaryDecisionTreesIsNPComplete.pdf) (1976). reference: [here](http://www.cbcb.umd.edu/~salzberg/docs/murthy_thesis/survey/node27.html)  

---

## 1 answers

### Answer by username_2 on 2011-08-25. Score: 16 | Accepted answer

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.18.9838&rep=rep1&type=pdf))

**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](http://www.sciencedirect.com/science/article/pii/S0022000007000815))

**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](http://blog.computationalcomplexity.org/2002/12/learning-via-occams-razor.html) 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](http://www.sciencedirect.com/science/article/pii/002001909290237P))
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](http://www.almaden.ibm.com/cs/people/vitaly/papers/ABFKP_Proper_Hardness_08.pdf))

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

> **Comments:**
> **username_2**: See bullet point #2 in the abstract here: http://researcher.watson.ibm.com/researcher/files/us-vitaly/ABFKP_Proper_Hardness_08.pdf  
> **username_4**: (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...  
> **username_2**: 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...  
> **username_4**: As far as I understand it, the algorithm evoked for 1. does not run in time $Poly(n,s)$ which would be necessary to get a contradiction with 2. (the precise result in the article if I got it correctly says that there is no polytime learning algorithm for decision trees). So there might be a problem with your argumentation.  
> **username_5**: 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?  

---

