About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
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.
Related
Conference paper
Dynamic Graph Convolutional Networks Using the Tensor M-Product
Conference paper