Algorithm for optimizing decision trees
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&#39;$ 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 &lt; 1$, one cannot find an equivalent decision tree $T&#39;$ 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:  


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