# What is the complexity of decision tree complexity?

Given a boolean function $f$ on $n$ bits, how hard is it to determine its decision tree complexity? (I assume the decision tree is simple, i.e., the allowed questions are the bits of the input.)

If $f$ is given by an oracle, then this is surely exponential in $n$, still I wonder if it ever has been studied, if there are algorithms that run in $2^{O(n)}$. I am even more interested in results about when $f$ is given in another way, by a polynomial over some field, or by a Turing-machine computing it. Is there anything known about this? Are there any hardness results?

• A very good reference: scottaaronson.com/papers/bfpsiam.pdf Nov 23 '14 at 19:46
• I'm wondering whether i currently understood the question; are the allowed queries on the form "is f(x) = 1"?. Herre x is some assignment to the variables. Nov 23 '14 at 22:08
• @Alessandro: Thx, perfect, exactly what I was looking for. Nov 23 '14 at 23:08

If you have an oracle for $f$, you can compute the optimal decision tree for $f$ in $O(3^nn)$ time and $O(3^n)$ space. Consider a function $g$ that takes as input a partition of the variables into three sets $T$, $F$, $S$ and outputs the size of the smallest decision tree for $f$ when the variables in $T$ are restricted to $1$ and the ones in $F$ are restricted to $0$ (and the remaining ones, in $S$, are unset). The following recurrence holds for $g$: $$g(T,F,S) = 1 + \min_{v \in S} g(T \cup {v},F,S\setminus \{v\}) + g(T,F \cup {v},S\setminus \{v\}).$$ The base case is that the function $f$ is constant with the given restriction, in which case $g$ is $0$. This recurrence directly leads to a dynamic programming algorithm. If, instead you are looking to compute the minimum depth of a decision tree then the following recurrence does the trick. $$g(T,F,S) = 1 + \min_{v \in S} \max\big{[}g(T \cup \{v\},F,S\setminus \{v\}), g(T,F \cup \{v\},S\setminus \{v\})\big{]}.$$
On the lower bound side, if $f$ is given in $k$-CNF then deciding whether the decision tree complexity is non-zero amounts to checking satisfiability which is hard to do in time $2^{o(n)}$ assuming Exponential Time Hypothesis (ETH) and in $1.999^n$ time assuming the Strong ETH.