Dual subimplicants of positive Boolean functions (Q4946700)

Let \(f=f(x_1,x_2,\dots ,x_n)\) be a positive (i.e. monotone nondecreasing) Boolean function and let \(f^d=\overline{f}(\overline{x}_1,\overline{x}_2,\dots ,\overline{x}_n)\) denote its dual. The co-occurrence graph associated with \(f\) has a vertex for every variable in \(f\) and an edge, if the corresponding two variables occur in at least one prime implicant of \(f.\) Given the family of index sets corresponding to the prime implicants of \(f\), and a subset \(\Delta \) of the variables, the Dual Subimplicant Recognition Problem (DSRP) asks, if there is a prime implicant of the dual \(f^d\) which contains all variables of \(\Delta \). By translating (DSRP) in a combinatorial problem on coverings it is shown that (DSRP) is NP-complete. This shows an inherent computational difficulty in Boolean dualization. If, however, the cardinality of \(\Delta \) is bounded by a constant, then (DSRP) becomes polynomially solvable. This has the consequence that the co-occurrence graph of the dual of a positive Boolean function \(f\) can be determined in polynomial time, even if \(f^d\) is of exponential size in the size of \(f.\)