<p>I think I can see a fairly easy reduction from 3DM. Let <span class="math-container">$B=\{0^J\}$</span>, i.e., it is a singleton set with the only zero element. The points of <span class="math-container">$A$</span> 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.</p>

<p>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 <span class="math-container">$\{0,1\}^J\setminus A$</span>.</p>

CC BY-SA 4.0
2020-02-15T16:44:21.747Z
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)?
Neal Young
CC BY-SA 4.0
2020-02-15T21:21:49.640Z
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$.
domotorp
CC BY-SA 4.0
2020-02-16T00:39:32.467Z
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?
Neal Young
CC BY-SA 4.0
2020-02-16T06:05:14.933Z
The depth equals the number of queries in the worst case, which happens for the leaf containing $B$.
domotorp
CC BY-SA 4.0
2020-02-16T17:26:46.680Z
Okay so we agree that the reduction should output $(J, A, B, n)$, and the description in the answer doesn't specify $n$.  The comment describing $n$ as "the depth of the leaf for $B$" doesn't clarify it for me, because I don't know what binary decision tree you have in mind (corresponding to a given 3D matching).  Indeed, I don't even see why there should be just one "leaf for $B$" in such a tree --- that comment suggests that you have in mind a tree that is essentially a path, but that doesn't seem right to me, because, to minimize depth, the tree is likely to be as balanced as possible.  (?)
Neal Young
CC BY-SA 4.0
2020-02-16T19:30:23.800Z
If $B$ is a singleton, then the tree does look like a path.
domotorp
CC BY-SA 4.0
2020-02-16T20:37:53.420Z
Oh in particular $B=\{0^J\}$, so for any allowed query $x_j=1$, a 'yes' answer rules out $B$?  (If $B$ were another singleton this would not be the case?)  But what should the depth be?  Consider an instance of 3DM with triples, say, $(1,5,6), (1,4,6), (1,4,5),(1,3,6), (1,3,5),(1,2,6)$.  So $A=(100011, 100101, 100110,101001,101010,110001)$. It has no 3D matching (it would have to be 2 triples matching all 6 elements).  But there is a decision tree of depth 1: to separate $B$ from all possible triples it suffices to check $x_j=1$.  I feel like I must be misunderstanding the reduction.  (?)
Neal Young
CC BY-SA 4.0
2020-02-16T20:43:09.857Z
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)$.
domotorp
CC BY-SA 4.0
2020-02-17T01:57:36.760Z
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.
Neal Young
CC BY-SA 4.0
2020-02-18T12:21:31.453Z
Thanks to both of you for suggesting and clarifying this construction. I particularly appreciate its simplicity. The idea of isolating the 0 renders the proof of correctness particularly simple.
Max Flow
CC BY-SA 4.0
2020-02-15T11:41:03.130Z
2020-02-15T11:41:03.130Z
domotorp
<p>I am interested in the computational complexity of</p>

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

<p>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 <a href="https://people.csail.mit.edu/rivest/HyafilRivest-ConstructingOptimalBinaryDecisionTreesIsNPComplete.pdf" rel="nofollow noreferrer">Hyafil and Rivest (1976)</a>. My understanding, however, is that they establish NP-completeness of the slightly different</p>

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

<p>Can anyone help me fill the gap or point me to other work establishing complexity results for <em>Problem 1</em>?</p>

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

<hr>

<p>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 <span class="math-container">$m = 2$</span>.</p>

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

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

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

CC BY-SA 4.0
2020-02-15T11:41:14.587Z
Related question: https://cstheory.stackexchange.com/questions/7563/algorithm-for-optimizing-decision-trees
domotorp
<np-hardness><machine-learning><boolean-functions><decision-trees>
Complexity of constructing minimum depth decision trees
Max Flow
# Complexity of constructing minimum depth decision trees

(Asked by: username_0 on 2020-02-14)

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)](https://people.csail.mit.edu/rivest/HyafilRivest-ConstructingOptimalBinaryDecisionTreesIsNPComplete.pdf). 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.

**Tags:** np-hardness, machine-learning, boolean-functions, decision-trees
> **Comments:**
> **username_1**: Related question: https://cstheory.stackexchange.com/questions/7563/algorithm-for-optimizing-decision-trees  

---

## 1 answers

### Answer by username_1 on 2020-02-15. Score: 5 | Accepted answer

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$.

> **Comments:**
> **username_2**: 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)?  
> **username_1**: 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$.  
> **username_2**: 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?  
> **username_1**: The depth equals the number of queries in the worst case, which happens for the leaf containing $B$.  
> **username_2**: Okay so we agree that the reduction should output $(J, A, B, n)$, and the description in the answer doesn't specify $n$.  The comment describing $n$ as "the depth of the leaf for $B$" doesn't clarify it for me, because I don't know what binary decision tree you have in mind (corresponding to a given 3D matching).  Indeed, I don't even see why there should be just one "leaf for $B$" in such a tree --- that comment suggests that you have in mind a tree that is essentially a path, but that doesn't seem right to me, because, to minimize depth, the tree is likely to be as balanced as possible.  (?)  
> **username_1**: If $B$ is a singleton, then the tree does look like a path.  
> **username_2**: Oh in particular $B=\{0^J\}$, so for any allowed query $x_j=1$, a 'yes' answer rules out $B$?  (If $B$ were another singleton this would not be the case?)  But what should the depth be?  Consider an instance of 3DM with triples, say, $(1,5,6), (1,4,6), (1,4,5),(1,3,6), (1,3,5),(1,2,6)$.  So $A=(100011, 100101, 100110,101001,101010,110001)$. It has no 3D matching (it would have to be 2 triples matching all 6 elements).  But there is a decision tree of depth 1: to separate $B$ from all possible triples it suffices to check $x_j=1$.  I feel like I must be misunderstanding the reduction.  (?)  
> **username_1**: 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)$.  
> **username_2**: 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.  
> **username_0**: Thanks to both of you for suggesting and clarifying this construction. I particularly appreciate its simplicity. The idea of isolating the 0 renders the proof of correctness particularly simple.  

---

