A fast and simple parallel algorithm for the monotone duality problem

Endre Boros, Kazuhisa Makino

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Citations (Scopus)

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 languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings
Pages183-194
Number of pages12
EditionPART 1
DOIs
StatePublished - Nov 12 2009
Event36th International Colloquium on Automata, Languages and Programming, ICALP 2009 - Rhodes, Greece
Duration: Jul 5 2009Jul 12 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume5555 LNCS

Other

Other36th International Colloquium on Automata, Languages and Programming, ICALP 2009
CountryGreece
CityRhodes
Period7/5/097/12/09

Fingerprint

Parallel algorithms

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Boros, E., & Makino, K. (2009). A fast and simple parallel algorithm for the monotone duality problem. In 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
Boros, Endre ; Makino, Kazuhisa. / A fast and simple parallel algorithm for the monotone duality problem. Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings. PART 1. ed. 2009. pp. 183-194 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).
@inproceedings{9fc72b5c04d449f1b42e84e758e6046f,
title = "A fast and simple parallel algorithm for the monotone duality problem",
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.",
author = "Endre Boros and Kazuhisa Makino",
year = "2009",
month = "11",
day = "12",
doi = "https://doi.org/10.1007/978-3-642-02927-1_17",
language = "English (US)",
isbn = "3642029264",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
number = "PART 1",
pages = "183--194",
booktitle = "Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings",
edition = "PART 1",

}

Boros, E & Makino, K 2009, A fast and simple parallel algorithm for the monotone duality problem. in 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.

Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings. PART 1. ed. 2009. p. 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).

Research output: Chapter in Book/Report/Conference proceedingConference 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 -

Boros E, Makino K. A fast and simple parallel algorithm for the monotone duality problem. In Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings. PART 1 ed. 2009. p. 183-194. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). https://doi.org/10.1007/978-3-642-02927-1_17