Given the prime CNF representation Φ of a monotone Boolean function f:{0,1}{sup}n→{0,1}, the dualization problem calls for finding the corresponding prime DNF representation Ψ of f. A very simple method (called Berge multiplication [2, Page 52-53]) works by multiplying out the clauses of Φ from left to right in some order, simplifying whenever possible using the absorption law. We show that for any monotone CNF Φ, Berge multiplication can be done in subexponential time, and for many interesting subclasses of monotone CNF's such as CNF's with bounded size, bounded degree, bounded intersection, bounded conformality, and read-once formula, it can be done in polynomial or quasi-polynomial time.
展开▼
