Algorithm Engineering for MONET and related covering problems

Description

 

Prof. Dr. Martin Mundhenk; University of Jena

 

Project website

 

Given two monotone boolean formulae in different normalforms, i.e. conjunctive and disjunctive normalform, the problem Monet asks about the equivalence of these two formulae. Without the restriction that both monotone formulae are given in different normalforms, the problem becomes coNP-complete in case of arbitrary monotone formulae or trivial in case of equal normalforms. Furthermore, the problem is coNP-complete for arbitrary boolean formlae in normalform. There is nothing known about the exact complexity of Monet, neither a polynomial upper bound nor a non-trivial lower bound. There are many algorithms for the decision and the computation problem - the best upper bound is quasi-polynomial in the length of input and output.
In particular, we want to compare the important algorithms, in due consideration of algorithm engineering. With this comparison, we hope for more information on hard instances for these algorithms and want to improve them. Also, there are many questions about new methods, e.g. randomization, multiplication and kernelization.
The area of applications in theory and practice is wide. Thus, we hope for many real world instances, e.g. from data mining or e-commerce.

In summary, our goals are

  • Implementation and comparison of several known algorithms, in due consideration of algorithm engineering
  • "Upgrades" for these algorithms, e.g. easy cases and data structures
  • Creation of a test-library with miscellaneous instances
  • New methods for solving the problem, e.g. randomization, multiplication and kernelization
  
[ Back ]