# Complexity of constructing minimum depth decision trees

I am interested in the computational complexity of

Problem 1: Given a finite, non-empty set $$J$$, given $$A, B \subseteq \{0,1\}^J$$ such that $$A \cap B = \emptyset$$, and given $$n \in \mathbb{N}$$, does there exist a binary decision tree of depth at most $$n$$ with decisions $$x_j \overset{?}{=} 1$$ for any $$x \in \{0,1\}^J$$ and any $$j \in J$$ such that, at any leaf of the tree, there are only elements of $$A$$ or only elements of $$B$$?

I often see claims of Problem 1 being NP-complete due to a famous reduction of 3-dimensional perfect matching, via exact cover by 3-sets, by Hyafil and Rivest (1976). My understanding, however, is that they establish NP-completeness of the slightly different

Problem 2: Given a finite, non-empty set $$J$$, given $$A \subseteq \{0,1\}^J$$ and given $$n \in \mathbb{N}$$, does there exist a binary decision tree of depth at most $$n$$ with decisions $$x_j \overset{?}{=} 1$$ for any $$x \in \{0,1\}^J$$ and any $$j \in J$$ such that, at any leaf of the tree, there is at most one element of $$A$$?

Can anyone help me fill the gap or point me to other work establishing complexity results for Problem 1?

Remark: While Hyafil and Rivest (1976) establish a result for an average depth, their argument is easily adapted to the minimum depth.

One further remark (risking to make the question seem less relevant to some): Consider the following generalization of Problem 1 that specializes to the latter for $$m = 2$$.

Problem 3: Given a finite, non-empty set $$J$$, given $$m \in \mathbb{N}$$, given pairwise disjoint $$A_1, \ldots, A_m \subseteq \{0,1\}^J$$, and given $$n \in \mathbb{N}$$, does there exist a binary decision tree of depth at most $$n$$ with decisions $$x_j \overset{?}{=} 1$$ for any $$x \in \{0,1\}^J$$ and any $$j \in J$$ such that, at any leaf of the tree, there are elements of at most one of the sets $$A_1, \ldots, A_m$$?

Problem 2 is polynomially reducible to Problem 3, for instance, by defining for each $$a \in A$$ of Problem 1 a separate subset $$A_a = \{a\}$$ of Problem 3. This reduction requires, however, that we can choose $$m = |A|$$. It is not generally possible in the special case of Problem 3 where $$m = 2$$, which is Problem 1.

At the same time, reducibility of Problem 2 to Problem 3 is sufficient for many informal claims, e.g., of exact learning of binary classification trees from examples being NP-hard due to Hyafil and Rivest (1976), or of extending partial pseudo-Boolean functions by minimum depth decision trees being NP-hard due to Hyafil and Rivest (1976). I just do not see how this holds for two-class classification and Boolean functions, respectively.

I think I can see a fairly easy reduction from 3DM. Let $$B=\{0^J\}$$, i.e., it is a singleton set with the only zero element. The points of $$A$$ correspond to the points of the 3DM that are to be matched. If a triple is matchable, then there is a coordinate where these 3 points are 1, while all other points are 0. The equivalence is straightforward.
I think an interesting question left open is if A is given (as part of the input), and our goal is to separate it from $$\{0,1\}^J\setminus A$$.
• What depth limit $n$ does your reduction output? Also, how does a 3D-matching for the given instance correspond to a BDD of depth at most $n$ (for the Problem 1 instance the reduction produces)? Feb 15 '20 at 16:44
• What do you mean by depth limit? I imagine that the 3DM has 3*n points that are to be matched, so $|A|=3n$. Which each question we can separate at most 3 members of $A$ from $B$. Feb 15 '20 at 21:21
• You're intending to reduce 3DM to Problem 1 in the post, right? That problem asks for a binary decision tree of depth at most a given value ($n$)... Am I missing something? Are you perhaps thinking of number of queries instead of depth? Feb 16 '20 at 0:39
• Yes, there is a great misunderstanding. This is converted to $A=(1,2,3,4,5,6)$, and the coordinates are indexed with $(156, 146, 145, 136, 135, 126)$, so with standard notation we would get $A=(111111,000001,000110,011000,101010,110101)$. Feb 16 '20 at 20:43
• Thanks for your patience! So given a 3D matching instance -- a set of triples $X$ from universe of elements $\{1,2,\ldots,3n\}$, the reduction outputs an instance of Problem 1 with $J$ equal to $|X|$, $B=\{0^J\}$, depth limit equal to $n$, and $A=\{A_1, A_2, \ldots, A_{3n}\}$ where $A_{ij} = 1$ if element $i$ is in triple $j$ (else $A_{ij}=0$). So the $A_i$s that pass the test $x_j=1$ (separating them from $B$) correspond to the elements $i$ in the triple $j$. So, a sequence of $n$ tests that separate all $A_i$s from $B$ corresponds to a sequence of triples that contain all the elements. Feb 17 '20 at 1:57