A fast and simple parallel algorithm for the monotone duality problem

Endre Boros, Kazuhisa Makino

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

14 Scopus citations

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 - 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
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

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

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'A fast and simple parallel algorithm for the monotone duality problem'. Together they form a unique fingerprint.

Cite this