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.