On the geometric separability of Boolean functions

Abstract

We investigate the complexity of the MEMBERSHIP problem for some geometrically defined classes of Boolean functions, i.e., the complexity of deciding whether a Boolean function given in DNF belongs to the class. We give a general argument implying that this problem is co-NP-hard for any class having some rather benign closure properties. Applying this result we show that the MEMBERSHIP problem is co-NP-complete for the class of linearly separable functions, threshold functions of order k (for any fixed k ≥ O), and some binary-parameter analogues of these classes. Finally, we obtain that the considered problem for unions of k ≥ 3 halfspaces is NP-hard, co-NP-hard and belongs to Σp2, and that the optimal threshold decomposition of a Boolean function as a union of halfspaces cannot even be efficiently approximated in a very strong sense unless P = NP. In some cases we improve previous hardness results on the considered problems.