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

Let f : {0, 1}(n) --> {0, 1} be a monotone Boolean function whose value at any point x is an element of {0, 1}(n) can be determined in time t. Denote by c = boolean AND(i is an element of C) boolean ORi is an element of I x(i ) the irredundant CNF of f, where C is the set of the prime implicates of f . Similarly, let d = boolean ORJ is an element of D boolean AND(j is an ele ment of J) x(j) 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' subset of or equal to C and D' subset of or equal to D such that (C', D') not equal ( C, D), a new term in (C\C')boolean OR(D\D') can be found in time O(n(t + n) )+ m(o(log m)), where m = \C'\ + \D'\. In particular, if f(x) can be evalua ted for every x is an element of {0, 1}(n) in polynomial time, then the for ms c and d can be jointly generated in incremental quasi-polynomial time. O n the other hand, even for the class of boolean AND, boolean OR-formulae f of depth 2, i.e., for CNFs or DNFs, it is unlikely that uniform sampling fr om within the set of the prime implicates and implicants of f can be carrie d out in time bounded by a quasi-polynomial 2(polylog(.)) in the input size of f. We also show that for some classes of polynomial-time computable mon otone 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 t otal (or incremental) quasi-polynomial time. Such classes of monotone Boole an functions naturally arise in game theory, networks and relay contact cir cuits, convex programming, and include a subset of boolean AND, boolean OR- formulae of depth 3. (C) 1999 Elsevier Science B.V. All rights reserved.