Theoretical Tractability vs. Practical Computation

Over the past years, we have been experiencing a rapid progress of business process automation and a pervasion of virtually all aspects of life by computers. Consequently, computational solutions are needed for increasingly hard problems in a great variety of fields. However, the intractability (i.e., NP-completeness or even higher complexity) of many important problems is a strong obstacle to the design of efficient solutions. Two major lines of research have been pursued in response to this situation: Parameterized complexity and the study of fixed-parameter algorithms have evolved as a very active research area and a lot of progress has been made in identifying tractable fragments of many hard problems. However, a theoretical tractability result as such does, in general, not automatically yield a computer program which actually runs efficiently in practice. Powerful tools have been making enormous progress in solving even intractable problems, among them most notably SAT solvers and datalog systems like DLV. Of course, we cannot expect these tools to cope with any real- world instances of an intractable problem. But they do perform reasonably well in many cases. However, a typical shortcoming of these tools is that, in general, they do not take advantage of tractable fragments of hard problems, i.e., although a problem instance falls into a theoretically easy subclass, the resources needed for solving it are essentially the same as with really hard problem instances. The primary goal of the proposed project is to combine the power of strong theoretical tractability results with the power of the advanced software tool DLV in order to allow for an efficient solution of many practically relevant problems. The key to this combination of theory and practice is an efficient fragment of datalog, which has recently been proposed for tackling a big class of problems with tractable fragments. We want to further pursue this method in order to make progress concerning the following three objectives of the project: 1. On the system side, we aim at an enhancement of DLV by making theoretical tractability results accessible to it. 2. On the theory side, we look for novel tractability results. 3. On the application side, we plan the development of algorithms for many (tractable fragments of) hard problems in a great variety of fields.

Viele praktisch relevante Probleme, insbesondere im Bereich des logischen Schließens, sind aufwändig zu berechnen. Eine vielversprechende Möglichkeit, um mit dieser hohen Berechnungskomplexität zurechtzukommen, ist die Suche nach effizient lösbaren Fragmenten von grundsätzlich schweren Problemen. Hierbei interessiert man sich für Einschränkungen der Probleminstanzen, die das betrachtete Problem effizient lösbar machen. Das Gebiet der parametrisierten Komplexitätstheorie, als relative junges Teilgebiet der Theoretischen Informatik, beschäftigt sich mit der Suche nach effizient lösbaren Fragmenten in Bezug auf gewisse Problemparameter. Das bedeutet, dass die Instanzen innerhalb eines solchen Fragments durch einen oder mehrere Parameter charakterisiert werden, wobei diese Parameter hinreichend klein sein müssen. Allerdings wurde in der Vergangenheit oft eine große Kluft zwischen theoretisch effizient lösbaren Problemen und der effizienten Berechenbarkeit in der Praxis beobachtet. Dies gilt insbesondere für jene theoretisch effizienten Fragmente, die mit Hilfe des Satzes von Courcelle bestimmt wurden. Dieser Satz charakterisiert eine umfangreiche Klasse von Problemen, die effizient lösbar werden, wenn die der Instanz zugrundeliegende Struktur ein Baum oder beinahe ein Baum ist. Das Hauptziel dieses Projektes war es, die theoretisch effiziente Lösbarkeit, die mittels dem Satz von Courcelle oder anderer Methoden der parametrisierten Komplexitätstheorie gezeigt wurde, in Lösungsverfahren überzuführen, die nun auch praxistauglich sind. Als ersten Schritt haben wir den Ansatz von (Gottlob, Pichler und Wei, 2007), der auf der deklarativen Programmiersprache Datalog aufbaut, erweitert und angewendet. Als weiteren Ansatz haben wir neue effiziente Algorithmen für verschiedenste Probleme im Bereich des logischen Schließens mit Hilfe der Technik der dynamischen Programmierung entwickelt. Dabei wurde dem Answer-Set Programming (ASP) Problem besondere Aufmerksamkeit gewidmet. Einerseits haben wir ASP als Werkzeug genutzt, um verschiedenste Probleme effizient zu lösen, andererseits haben wir auch neue Methoden entwickelt, die ASP selbst effizienter machen. Als erster Parameter wurde im Rahmen unserer Suche nach effizienten Algorithmen die sogenannte Baumweite betrachtet. Dieser Parameter misst die Ähnlichkeit der Instanz zu einem Baum. Abgesehen von der Entwicklung neuer Algorithmen, die sich niedrige Baum- weite zunutze machen, wurden praktische Aspekte der Berechnung von Baumzerlegungen erforscht. Unsere Suche nach effizient lösbaren Fragmenten bezüglich der Baumweite wurde dann auch auf andere Parameter erweitert. Hierbei wurden zahlreiche neue effizient lösbare Fragmente von schweren Problemen im Bereich des logischen Schließens durch die Betrachtung einer Vielzahl von Problemparametern entdeckt. Außerdem konnten wir die Grenzen dieser Vorgangsweise durch neue Resultate aufzeigen, die eine effiziente Lösbarkeit unter üblichen, komplexitätstheoretischen Annahmen ausschließen.