On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions Original Research Article

Let f:{0,1}n→{0,1} be a monotone Boolean function whose value at any point x∈{0,1}n can be determined in time t. Denote by c=⋀I∈C ⋁i∈I xi the irredundant CNF of f, where C is the set of the prime implicates of f. Similarly, let d=⋁J∈D ⋀j∈J xj be the irredundant DNF of the same function, where D is the set of the prime implicants of f. We show that given subsets C′⊆C and D′⊆D such that (C′,D′)≠(C,D), a new term in (C⧹C′)∪(D⧹D′) can be found in time O(n(t+n))+mo(log m), where m=|C′|+|D′|. In particular, if f(x) can be evaluated for every x∈{0,1}n in polynomial time, then the forms c and d can be jointly generated in incremental quasi-polynomial time. On the other hand, even for the class of ∧,∨-formulae f of depth 2, i.e., for CNFs or DNFs, it is unlikely that uniform sampling from within the set of the prime implicates and implicants of f can be carried out in time bounded by a quasi-polynomial 2polylog(·) in the input size of f. We also show that for some classes of polynomial-time computable monotone Boolean functions it is NP-hard to test either of the conditions D′=D or C′=C. This provides evidence that for each of these classes neither conjunctive nor disjunctive irredundant normal forms can be generated in total (or incremental) quasi-polynomial time. Such classes of monotone Boolean functions naturally arise in game theory, networks and relay contact circuits, convex programming, and include a subset of ∧,∨-formulae of depth 3.