Hagen, M: Algorithmic and Computational Complexity Issues

In this thesis, we study the problem Monet¿the Mo(notone) n(ormal form)
e(quivalence) t(est)¿that asks to decide equivalence of a monotone disjunctive normal form . and a monotone conjunctive normal form ?. This problem is a covering problem that can be interpreted as the task of enumerating all (in some sense) minimal solutions of some system. Hence, there is a huge number of similar questions in many problems from diverse applications.Our results can roughly be divided into results on the design and evaluation of algorithms for Monet and results that rather touch complexity questions related to the problem. As for the algorithmic part, we will give lower bounds for several known algorithms and report results obtained by practically examining the theoretically
fastest algorithm in computational experiments. As for the complexity
part of this thesis, we show several restricted classes of the problem to be solvable in logarithmic space, which improves previously known polynomial time bounds. We also show Monet to be in the complexity class of .xed-arameter tractable problems with respect to several parameters. More precisely, we prove the following main results using various algorithmic and computational complexity techniques. - Several restricted classes of Monet are solvable in logarithmic space. In
particular, these are the classes where the DNF- contains only a constant number of monomials (Section 4.1.1), contains only monomials of constant size (Section 4.1.2), contains only monomials that each do not contain only a constant number of variables
(Section 4.1.3),- is regular (Section 4.2.1), aligned (Section 4.2.2), or 2-monotonic (Section 4.2.3).- The DL-algorithm (Section 5.1.2), the BMR-algorithm (Section 5.1.3), the KS-algorithm (Section 5.1.4), and the HBC-algorithm (Section 5.2) for the
problem Monet are not output-polynomial. Their running times are at
least nÙ(log log n), where n denotes the size of the input and output.-FK-algorithm B for the