de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

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.


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