Positive and Horn decomposability of partially defined Boolean functions Original Research Article

We consider the decomposability of partially defined Boolean functions under given schemes, along the line developed in [2]. For two positive schemes, whose complexity was left open in [2], we prove their NP-completeness. We then consider Horn schemes and mixed schemes (mixture of positive and Horn functions), and obtain computationally efficient algorithms in some cases, but prove NP-completeness in other cases.