1
$\begingroup$

How many boolean function with $n$ variables with decision tree complexity $k$?

By decision tree complexity of a function $f$ I mean the smallest depth among all deterministic decision trees that computes $f$.

Approximation results, bounds, efficient algorithms to find the value are interested for me.

I know only the following simple fact: if boolean function $f$ with $n$ variables has complexity less than $n$ then relative Hamming distance between $f$ and XOR is $\frac{1}{2}$. (This implies an upper bound for the number of such functions.)

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Well, it's at most $(2n)^{2^k}$. Or slightly better, $n(n-1)^2(n-2)^4\cdots(n-k+1)^{2^{k-1}}2^{2^k}$. $\endgroup$
    – Emil Jeřábek
    Commented Aug 21, 2023 at 7:25
  • $\begingroup$ @EmilJeřábek Could you please explain? $\endgroup$
    – Alexey Milovanov
    Commented Aug 21, 2023 at 17:11
  • 1
    $\begingroup$ Just count the number of decision trees of depth $k$. You may assume that it’s the perfect binary tree of the given depth. There are $2^k-1$ inner nodes, hence $n^{2^k-1}$ choices for the query variables, and for each of the $2^k$ leaves, you have two choices for the output value. For the second bound, you may assume that no variable is queried twice along the same path, reducing the number of possibilities for the query variables at each level. $\endgroup$
    – Emil Jeřábek
    Commented Aug 21, 2023 at 19:09
  • $\begingroup$ A similar argument which gives the second bound but allows any improvement to propagate is to say that if $B(n, k)$ counts the number of distinct Boolean functions on $n$ variables with decision tree complexity $k$ then $B(n, k) \le n B(n-1, k-1)^2$: choose the variable for the first decision from the $n$ available and then remove it from consideration. $\endgroup$
    – Peter Taylor
    Commented Aug 22, 2023 at 15:38
  • $\begingroup$ One improvement is to argue by induction that if a variable $x$ is queried on every path from the root to a leaf then there is a rearranged tree of the same height which puts $x$ at the root. Then if you have $m$ variables which are queried on every path, that gives a (not tight in general) lower bound of $m!$ on the size of the equivalence class of trees which are equivalent if they represent the same function. I haven't tried to calculate better bounds on $B(n, k)$ using this argument. $\endgroup$
    – Peter Taylor
    Commented Aug 22, 2023 at 15:42

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .