TY - GEN

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

AU - Elbassioni, Khaled M.

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33750732625&partnerID=8YFLogxK

U2 - 10.1007/11841036_32

DO - 10.1007/11841036_32

M3 - Conference contribution

AN - SCOPUS:33750732625

SN - 3540388753

SN - 9783540388753

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 340

EP - 351

BT - Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings

PB - Springer Verlag

T2 - 14th Annual European Symposium on Algorithms, ESA 2006

Y2 - 11 September 2006 through 13 September 2006

ER -