TY - GEN
T1 - A fast and simple parallel algorithm for the monotone duality problem
AU - Boros, Endre
AU - Makino, Kazuhisa
PY - 2009
Y1 - 2009
N2 - We consider the monotone duality problem i.e., checking whether given monotone CNF φ and DNF ψ are equivalent, which is a prominent open problem in NP-completeness. We construct a fast and simple parallel algorithms for the problem, that run in polylogarithmic time by using quasi-polynomially many processors. The algorithm exhibits better parallel time complexity of the existing algorithms of Elbassioni [11]. By using a different threshold of the degree parameter ε of φ in the algorithm, we also present a stronger bound on the number of processors for polylogarithmic-time parallel computation and improves over the previously best known bound on the sequential time complexity of the problem in the case when the magnitudes of |φ|, |ψ| and n are different, e.g., |ψ|=|φ| α ≫ n for α>1, where n denotes the number of variables. Furthermore, we show that, for several interesting well-known classes of monotone CNFs φ such as bounded degree, clause-size, and intersection-size, our parallel algorithm runs polylogarithmic time by using polynomially many processors.
AB - We consider the monotone duality problem i.e., checking whether given monotone CNF φ and DNF ψ are equivalent, which is a prominent open problem in NP-completeness. We construct a fast and simple parallel algorithms for the problem, that run in polylogarithmic time by using quasi-polynomially many processors. The algorithm exhibits better parallel time complexity of the existing algorithms of Elbassioni [11]. By using a different threshold of the degree parameter ε of φ in the algorithm, we also present a stronger bound on the number of processors for polylogarithmic-time parallel computation and improves over the previously best known bound on the sequential time complexity of the problem in the case when the magnitudes of |φ|, |ψ| and n are different, e.g., |ψ|=|φ| α ≫ n for α>1, where n denotes the number of variables. Furthermore, we show that, for several interesting well-known classes of monotone CNFs φ such as bounded degree, clause-size, and intersection-size, our parallel algorithm runs polylogarithmic time by using polynomially many processors.
UR - http://www.scopus.com/inward/record.url?scp=70350402445&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70350402445&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-02927-1_17
DO - 10.1007/978-3-642-02927-1_17
M3 - Conference contribution
AN - SCOPUS:70350402445
SN - 3642029264
SN - 9783642029264
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 183
EP - 194
BT - Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings
T2 - 36th International Colloquium on Automata, Languages and Programming, ICALP 2009
Y2 - 5 July 2009 through 12 July 2009
ER -