Inapproximability of a Pair of Forms Defining a Partial Boolean Function
This addresses a theoretical computational complexity problem for researchers in Boolean function optimization, showing incremental hardness results for specific forms.
The paper tackles the problem of jointly minimizing forms of two Boolean functions to separate disjoint sets, hypothesizing it might be easier than minimizing a single function, but refutes this for forms like binary decision trees and OBDDs, showing no o(ln(|A|+|B|-1))-approximation exists unless P=NP.
We consider the problem of jointly minimizing forms of two Boolean functions $f, g \colon \{0,1\}^J \to \{0,1\}$ such that $f + g \leq 1$ and so as to separate disjoint sets $A \cup B \subseteq \{0,1\}^J$ such that $f(A) = \{1\}$ and $g(B) = \{1\}$. We hypothesize that this problem is easier to solve or approximate than the well-understood problem of minimizing the form of one Boolean function $h: \{0,1\}^J \to \{0,1\}$ such that $h(A) = \{1\}$ and $h(B) = \{0\}$. For a large class of forms, including binary decision trees and ordered binary decision diagrams, we refute this hypothesis. For disjunctive normal forms, we show that the problem is at least as hard as MIN-SET-COVER. For all these forms, we establish that no $o(\ln (|A| + |B| -1))$-approximation algorithm exists unless P$=$NP.