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?

  • 4
    $\begingroup$ A very good reference: scottaaronson.com/papers/bfpsiam.pdf $\endgroup$ – Alessandro Cosentino Nov 23 '14 at 19:46
  • $\begingroup$ 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. $\endgroup$ – daniello Nov 23 '14 at 22:08
  • $\begingroup$ @Alessandro: Thx, perfect, exactly what I was looking for. $\endgroup$ – domotorp 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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