Theoretisch Effiziente Lösbarkeit vs, Praktische Berechnung

Durch die stetige Zunahme der Automatisierung, nicht nur in wirtschaftlichen, sondern in nahezu allen Bereichen unseres Lebens, sowie die immer größeren Mengen an zu verarbeitenden Daten gilt die Suche nach effizienten Algorithmen mehr denn je als wichtiges Gebiet der (theoretischen) Informatik. Da vielen wichtigen Problemstellungen jedoch ein inhärent hoher Berechnungsaufwand (die sogenannte NP-Vollständigkeit oder noch höhere Komplexität) innewohnt, sind allgemein-effiziente Methoden zur Lösung solcher Probleme nicht möglich. Es gibt daher zwei wichtige Forschungsansätze, um mit dieser Situation umzugehen: Das aktuelle Forschungsgebiet der parametrisierten Komplexität und der sogenannten "Fixed-Parameter Algorithmen" versucht, Problemstellungen auf eine Teilklasse des jeweiligen Problems so einzugrenzen, dass das Finden effizienter Algorithmen nun (zumindest) theoretisch möglich ist. Es hat sich aber herausgestellt, dass es von der theoretisch effizienten Lösbarkeit eines Problems bis zu einer praktisch tatsächlich effizienten Berechnung noch ein sehr weiter Weg ist. Eine stetige Verbesserung der allgemeinen Lösungsalgorithmen (für inhärent schwierige Probleme) plus die steigende Rechenleistung erlauben es ausgereiften Systemen (insbesondere aus den Bereichen SAT oder der logischen Programmierung bzw. Datalog), nun viele - auch sehr große - Instanzen des Problems in annehmbaren Laufzeiten zu lösen. Allerdings nutzen diese Systeme zumeist noch keine Tests, ob eine gegebene Probleminstanz in eine der oben genannten effizient lösbaren Teilklassen fällt, wodurch ein möglicher besserer Lösungsweg nicht erkannt wird. Im vorgeschlagenen Projekt setzen wir uns zum Ziel, erstgenannte theoretische Resultate mit der bereits bestehenden Ausgereiftheit des Datalog-Systems DLV zu kombinieren, um Berchnungsprobleme von praktischer Relevanz effizient zu lösen. Der angedachten Methode liegt ein spezielles Fragment von Datalog zu Grunde, welches eine allgemeine Nutzung von Fixed-Parameter Algorithmen erlaubt. Das Anwenden und Verfeinern dieser Methode erlaubt uns, wesentliche Forschungsergebnisse in drei Zielrichtungen in Aussicht zu stellen: 1. Software: Implementierung einer Erweiterung von DLV, um Problemfragmente von niedriger parametrisierter Komplexität erkennen und effizient lösen zu können. 2. Theorie: Neue Resultate um solche Problemfragmente zu erweitern oder zu ergänzen. 3. Anwendung: Entwickeln neuer, effizienter Algorithmen (mittels Datalog) für konkrete Problemstellungen aus verschiedenen Gebieten der Informatik.

Many practically relevant problems in particular in the area of Reasoning are computa- tionally hard. A promising way of dealing with high computational complexity is to search for so-called tractable fragments of otherwise intractable problems. One is thus interested in restrictions on problem instances which make the problem at hand efficiently solvable. Parameterized Complexity as a relatively young subfield of Theoretical Computer Science aims at identifying tractable fragments in terms of problem parameters, i.e., the problem instances in such a fragment are characterized by one or more problem parameters and by the restriction that these parameters must be small. However, it has been observed that there is often a big gap between theoretical tractability and efficient computation in practice. This is in particular the case for most tractability results obtained via Courcelles Theorem, which characterizes a big class of problems that become tractable if the underlying structure of a problem instance is a tree or almost a tree. The principal goal of this project was to turn such theoretical tractability results obtained by Courcelles Theorem or other methods from Parameterized Complexity into efficient computation in practice. In the first place, we have applied and further extended an approach proposed by (Gottlob, Pichler, and Wei, 2007) based on the declarative programming language Datalog. As an alternative approach, we have developed new efficient algorithms based on dynamic programming for several hard Reasoning problems. Particular emphasis has been put on one specific Reasoning method, namely Answer-Set Programming (ASP). On the one hand, we have used ASP as a tool to solve other problems efficiently. On the other hand, we have also developed new methods for solving ASP itself efficiently. The first parameter that we have investigated in our search for efficient algorithms based on theoretical tractability results is treewidth. This parameter measures the tree-likeness of an instance. Apart from developing new algorithms that exploit low treewidth of several problems, we have also studied several practical aspects of tree decompositions. Our study of tractable fragments of hard problems was then extended from treewidth to further parameters. We have identified new tractable fragments of hard Reasoning problems by studying various problem parameters of these problems. Moreover, we have also pinpointed the boundaries of tractability by proving new intractability results.