On the complexity of the multiplication method for monotone CNF/DNF dualization

Given the irredundant CNF representation φ of a monotone Boolean function f : {0, 1}ⁿ → {0, 1}, the dualization problem calls for finding the corresponding unique irredundant DNF representation Ψ of f. The (generalized) multiplication method works by repeatedly dividing the clauses of φ into (not necessarily disjoint) groups, multiplyingout the clauses in each group, and then reducing the result by applying the absorption law. We present the first non-trivial upper-bounds on the complexity of this multiplication method. Precisely, we show that if the grouping of the clauses is done in an output-independent way, then multiplication can be performed in sub-exponential time (n|ψ|)^o(√|φ|)|φ| ^{o(log n)}. On the other hand, multiplication can be carriedout in quasi-polynomial time poly(n, |ψ|) · |φ|^o(log|ψ|) provided that the grouping is done depending on the intermediate outputs produced during the multiplication process.