7
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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)? $\endgroup$
    – Neal Young
    Commented Feb 15, 2020 at 16:44
  • $\begingroup$ 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$. $\endgroup$
    – domotorp
    Commented Feb 15, 2020 at 21:21
  • $\begingroup$ 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? $\endgroup$
    – Neal Young
    Commented Feb 16, 2020 at 0:39
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – domotorp
    Commented Feb 16, 2020 at 20:43
  • 2
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Commented Feb 17, 2020 at 1:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.