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

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

CC BY-SA 3.0
2014-11-23T19:47:02.717Z
2014-11-23T20:36:33.120Z
2014-11-23T20:36:33.120Z
daniello
<p>Given a boolean function $f$ on $n$ bits, how hard is it to determine its <a href="http://en.wikipedia.org/wiki/Decision_tree_model">decision tree complexity</a>?
(I assume the decision tree is simple, i.e., the allowed questions are the bits of the input.)</p>

<p>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?</p>

CC BY-SA 3.0
2014-11-23T19:46:43.690Z
A very good reference: http://www.scottaaronson.com/papers/bfpsiam.pdf
Alessandro Cosentino
CC BY-SA 3.0
2014-11-23T22:08:01.960Z
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.
daniello
CC BY-SA 3.0
2014-11-23T23:08:07.013Z
@Alessandro: Thx, perfect, exactly what I was looking for.
domotorp
<cc.complexity-theory><decision-trees>
What is the complexity of decision tree complexity?
domotorp
# What is the complexity of decision tree complexity?

(Asked by: username_0 on 2014-11-23)

Given a boolean function $f$ on $n$ bits, how hard is it to determine its [decision tree complexity](http://en.wikipedia.org/wiki/Decision_tree_model)?
(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?

**Tags:** cc.complexity-theory, decision-trees
> **Comments:**
> **username_1**: A very good reference: http://www.scottaaronson.com/papers/bfpsiam.pdf  
> **username_2**: 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.  
> **username_0**: @Alessandro: Thx, perfect, exactly what I was looking for.  

---

## 1 answers

### Answer by username_2 on 2014-11-23. Score: 6 | Accepted answer

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.


---

