A Fast and Simple Parallel Algorithm for the Monotone Duality Problem

given monotone CNF f and DNF g 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.
By using a different threshold of the degree
parameter $epsilon$ of $g$ 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 $f$, $g$ and $n$ are
different, e.g., $|g|=|f|^alpha >> n$ for $alpha >1$,
where $n$ denotes the number of variables.
Furthermore, we show that,
for several interesting well-known classes of monotone CNFs f
such as bounded degree, clause-size, and intersection-size,
our parallel algorithm runs
polylogarithmic time by using polynomially many processors.

This is a joint work with Endre Boros (Rutgers University).