Dual subimplicants of positive Boolean functions
Endre Boros, Vladimir Gurvich, Peter L. Hammer · Optimization methods & software · 1998
Given a positive Boolean function fand a subset δ of its variables, we give a combinatorial condition characterizing the existence of a prime implicant Dˆof the Boolean dual f d of f having the property that every variable in δ appears in Dˆ We show that the recognition of this property is an NP-complete problem, suggesting an inherent computational difficulty of Boolean dualization, independently of the size of the dual function. Finally it is shown that if the cardinality of δ is bounded by a constant, then the above recognition problem is polynomial. In particular, it follows that the co-ocurrence graph of the dual of a positive Boolean function can be always generated in time polynomial in the size of the function.