| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429217 | Information Processing Letters | 2007 | 5 Pages |
Abstract
We consider the problem Monet—given two monotone formulas φ in DNF and ψ in CNF, decide whether they are equivalent. While Monet is probably not coNP-hard, it is a long standing open question whether it has a polynomial time algorithm and thus belongs to P. In this paper we examine the parameterized complexity of Monet. We show that Monet is in FPT by giving fixed-parameter algorithms for different parameters.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
