Logarithmic Space Instances of Monotone Normal Form Equivalence Testing

by    Matthias Hagen

Preprint series: 06-10, Reports on Computer Science

MSC:
68Q25 Analysis of algorithms and problem complexity [See also 68W40]

Abstract: We examine the problem
MONE---given a monotone DNF and
a monotone CNF, decide whether they are
equivalent.
The exact complexity of MONE
is a long standing open problem.
On the one hand, MONE is probably
not coNP-complete.
But on the other hand, MONE is
not known to be in P,
although for numerous restrictions
on the input formulas polynomial
time algorithms exist.
We improve the resource bound
for several of these 'easy' instances
of MONE by showing that actually
logarithmic space suffices
for their decision.
Among these instances are MONE-instances
with a DNF that is regular, aligned,
2-monotonic, or that contains only very
large monomials.

Keywords: monotone normal form, equivalence, logarithmic space algorithm

Upload: 2006-06-29

Update: 2006-07-04 -07 -04


The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.