7

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.

Max Flow
  • 193
  • 5
  • Related question: https://cstheory.stackexchange.com/questions/7563/algorithm-for-optimizing-decision-trees – domotorp Feb 15 '20 at 11:41

1 Answers1

5

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

domotorp
  • 13,931
  • 37
  • 93
  • 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 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$. – domotorp 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? – Neal Young Feb 16 '20 at 00:39
  • The depth equals the number of queries in the worst case, which happens for the leaf containing $B$. – domotorp Feb 16 '20 at 06:05
  • 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 Feb 16 '20 at 17:26
  • If $B$ is a singleton, then the tree does look like a path. – domotorp Feb 16 '20 at 19:30
  • 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 Feb 16 '20 at 20:37
  • 2
    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 Feb 16 '20 at 20:43
  • 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. – Neal Young Feb 17 '20 at 01:57
  • 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 Feb 18 '20 at 12:21