Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
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.
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
Andrew Skumanich
SPIE Optics Quebec 1993
Karthik Visweswariah, Sanjeev Kulkarni, et al.
IEEE International Symposium on Information Theory - Proceedings
Imran Nasim, Michael E. Henderson
Mathematics