hide
Free keywords:
-
Abstract:
Given the irredundant CNF representation $\phi$ of a monotone Boolean function
$f:\{0,1\}^n\mapsto\{0,1\}$, the dualization problem calls for finding the
corresponding unique irredundant DNF representation $\psi$ of $f$. The
(generalized) multiplication method works by repeatedly dividing the clauses of
$\phi$ into (not necessarily disjoint) groups, multiplying-out 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|\psi|)^{O(\sqrt{|\phi|})}|\phi|^{O(\log n)}$. On the
other hand, multiplication can be carried-out in quasi-polynomial time
$\poly(n,|\psi|)\cdot|\phi|^{o(\log |\psi|)}$, provided that the grouping is
done depending on the intermediate outputs produced during the multiplication
process.
