Inapproximability of Minimizing a Pair of DNFs or Binary Decision Trees
  Defining a Partial Boolean Function
  The desire to apply machine learning techniques in safety-critical
environments has renewed interest in the learning of partial functions for
distinguishing between positive, negative and unclear observations. We
contribute to the understanding of the hardness of this problem. Specifically,
we consider partial Boolean functions defined by a pair of Boolean functions
$f, g \colon \{0,1\}^J \to \{0,1\}$ such that $f \cdot g = 0$ and such that $f$
and $g$ are defined by disjunctive normal forms or binary decision trees. We
show: Minimizing the sum of the lengths or depths of these forms while
separating disjoint sets $A \cup B = S \subseteq \{0,1\}^J$ such that $f(A) =
\{1\}$ and $g(B) = \{1\}$ is inapproximable to within $(1 - \epsilon) \ln
(|S|-1)$ for any $\epsilon > 0$, unless P=NP.
