ON THE GEOMETRIC SEPARABILITY OF BOOLEAN FUNCTIONS

We investigate the complexity of the MEMBERSHIP problem for some geome trically 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 t his result we show that the MEMBERSHIP problem is co-NP-complete for t he class of linearly separable functions, threshold functions of order k (for any fixed k greater than or equal to 0), and some binary-param eter analogues of these classes. Finally, we obtain that the considere d problem for unions of k greater than or equal to 3 halfspaces is NP- hard, co-NP-hard and belongs to Sigma(2)(p), and that the optimal thre shold decomposition of a Boolean function as a union of halfspaces can not even be efficiently approximated in a very strong sense unless P = NP. In some cases we improve previous hardness results on the conside red problems.