Algorithm Engineering für MONET und verwandte Abdeckungsprobleme

点击翻译按钮获取中文摘要

Der Äquivalenztest monotoner Boolescher Formeln in Normalform (Problem MONET) findet sich in vielen wichtigen Problemstellungen aus den unterschiedlichsten Bereichen der Informatik wieder. Es gibt sehr unterschiedliche Algorithmen für MONET, aber keiner davon hat polynomielle Rechenzeit. Ungeklärt ist, ob nur die bekannten Algorithmen nicht gut genug sind, oder ob es für MONET keinen schnellen Algorithmus geben kann. Umso interessanter und von praktischer Bedeutung ist damit die Frage, welcher der bekannten Algorithmen für welche Anwendungen am schnellsten ist. Im beantragten Projekt soll eine auf Experimenten basierende Studie einen Vergleich von sorgfältigen Implementierungen der bekannten Algorithmen ermöglichen. Hierzu suchen wir für jeden Algorithmus besonders schwer zu behandelnde Probleminstanzen. Diese Instanzen werden Teil einer im Zuge des Projektes zu erstellenden Online-MONET-Instanzen-Bibliothek. Schließlich soll experimentell untersucht werden, welche Modifikationen die bekannten Algorithmen verbessern. Die bisher kaum untersuchte Multiplikationsmethode bietet sich wegen ihrer Freiheitsgrade ganz besonders für eine Untersuchung mittels Algorithm Engineering an.