On the complexity of the multiplication method for monotone CNF/DNF dualization

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations


Given the irredundant CNF representation φ of a monotone Boolean function f : {0, 1}n → {0, 1}, the dualization problem calls for finding the corresponding unique irredundant DNF representation Ψ of f. The (generalized) multiplication method works by repeatedly dividing the clauses of φ into (not necessarily disjoint) groups, multiplyingout 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|ψ|)o(√|φ|)|φ| o(log n). On the other hand, multiplication can be carriedout in quasi-polynomial time poly(n, |ψ|) · |φ|o(log|ψ|) provided that the grouping is done depending on the intermediate outputs produced during the multiplication process.

Original languageBritish English
Title of host publicationAlgorithms, ESA 2006 - 14th Annual European Symposium, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540388753, 9783540388753
StatePublished - 2006
Event14th Annual European Symposium on Algorithms, ESA 2006 - Zurich, Switzerland
Duration: 11 Sep 200613 Sep 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4168 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference14th Annual European Symposium on Algorithms, ESA 2006


Dive into the research topics of 'On the complexity of the multiplication method for monotone CNF/DNF dualization'. Together they form a unique fingerprint.

Cite this