de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44374

Elbassioni,  Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Elbassioni, K. (2006). On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization. In Algorithms - ESA 2006, 14th Annual European Symposium (pp. 340-351). Berlin, Germany: Springer.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2394-8
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.