de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

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

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44374

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

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

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.

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.