DIMACS TR: 2007-15
Berge Multiplication for Monotone Boolean Dualization
Authors: Endre Boros, Khaled Elbassioni and Kazuhisa Makino
ABSTRACT
Given the prime CNF representation $\phi$ of a monotone Boolean function $f:\{0,1\}^n\mapsto\{0,1\}$, the dualization problem calls for finding the corresponding prime DNF representation $\psi$ of $f$. A very simple method (called {\em Berge multiplication} \cite[Page 52--53]{B89}) works by multiplying out the clauses of $\phi$ from left to right in some order, simplifying whenever possible using {\it the absorption law}. We show that for any monotone CNF $\phi$, 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.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2007/2007-15.pdf
DIMACS Home Page