### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings |

Pages | 183-194 |

Number of pages | 12 |

Edition | PART 1 |

DOIs | |

State | Published - Nov 12 2009 |

Event | 36th International Colloquium on Automata, Languages and Programming, ICALP 2009 - Rhodes, Greece Duration: Jul 5 2009 → Jul 12 2009 |

### Publication series

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

Number | PART 1 |

Volume | 5555 LNCS |

### Other

Other | 36th International Colloquium on Automata, Languages and Programming, ICALP 2009 |
---|---|

Country | Greece |

City | Rhodes |

Period | 7/5/09 → 7/12/09 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings*(PART 1 ed., pp. 183-194). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5555 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-02927-1_17

}

*Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings.*PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 5555 LNCS, pp. 183-194, 36th International Colloquium on Automata, Languages and Programming, ICALP 2009, Rhodes, Greece, 7/5/09. https://doi.org/10.1007/978-3-642-02927-1_17

**A fast and simple parallel algorithm for the monotone duality problem.** / Boros, Endre; Makino, Kazuhisa.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A fast and simple parallel algorithm for the monotone duality problem

AU - Boros, Endre

AU - Makino, Kazuhisa

PY - 2009/11/12

Y1 - 2009/11/12

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 - https://doi.org/10.1007/978-3-642-02927-1_17

DO - https://doi.org/10.1007/978-3-642-02927-1_17

M3 - Conference contribution

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

ER -