Dual subimplicants of positive Boolean functions

Given a positive Boolean function f and a subset Delta of its variables, we give a combinatorial condition characterizing the existence of a prime implicant (D) over cap of the Boolean dual f(d) of f, having the property that every variable in Delta appears in (D) over cap. 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 Delta is bounded by a constant, then the above recognition problem is polynomial. In particular, it follows that the co-occurrence graph of the dual of a positive Boolean function can be always generated in time polynomial in the size of the function.