by Matthias Hagen
Preprint series: 06-10, Reports on Computer Science
Abstract: We examine the problem
MONE---given a monotone DNF and
a monotone CNF, decide whether they are
The exact complexity of MONE
is a long standing open problem.
On the one hand, MONE is probably
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
Keywords: monotone normal form, equivalence, logarithmic space algorithm
Update: 2006-07-04 -07 -04