QuantASP - Quantitatives Schlussfolgern und Zählen für ASP

Ein zentraler Schwerpunkt in der Informatik ist das Lösen schwieriger Berechnungsprobleme. Unter diesen Problemen sind in den letzten Jahrzehnten zunehmend quantitative Fragestellungen in den Fokus gerückt. Diese betrachten nicht nur die Entscheidung der Existenz einer Lösung, sondern sind an der Gesamtanzahl aller Lösungen interessiert, was eine Vielzahl von Anwendungen in der computationalen Biologie, Künstlichen Intelligenz und im quantitativen Schlussfolgern mit sich bringt. Beispielsweise ergeben sich Rückschlüsse über die Wichtigkeit und Konsequenzen bestimmter Lösungsteile, je nachdem ob diese Teile in wenigen oder einigen Lösungen oder gar einer großen Mehrheit an Lösungen auftreten. Ein konkreter Ansatz, um Berechnungsprobleme zu lösen, verfolgt die Idee der Zerlegung der Probleminstanz in kleinere Teile, die danach Schritt für Schritt gelöst werden, um schließlich mittels geeigneter Kombination dieser Teillösungen zu einer Lösung des Gesamtproblems zu kommen. Dieser Ansatz ist unter Dynamischer Programmierung bekannt und bereits für verschiedene Problemstellungen angewendet worden, allerdings sind gerade bei Zählproblemen noch viele Fragen offen. Einige dieser offenen Fragen ergeben sich beim Zählen von Lösungen logischer Programme, welche mit Hilfe einer Menge von Regeln stabile (minimale) Antworten beschreiben, die alle Regeln erfüllt. Unsere Arbeitshypothese ist, dass die Stabilität der Antworten, die logische Programme fordern, der inherente Grund dafür ist, warum das Zählen von Antworten mittels Dynamischer Programmierung tatsächlich viel aufwändiger ist, als die Frage, ob überhaupt eine Antwort existiert. Dabei wollen wir zeigen, dass selbst bei strukturell einfacheren Instanzen, wo die Struktur der Programme nicht zu weit von baumähnlichen Strukturen abweicht (beschränkte Baumweite), Zählprobleme auf bestimmten Schlüsselfragmenten von Programmen deutlich aufwändiger zu lösen sind. Dies soll in weiterer Folge zu genauen unteren Laufzeitschranken (Härteresultate) führen und eine allgemeine und einfach anzuwendende Methode zum Zeigen dieser unteren Schranken für eine Liste weiterer Probleme liefern. Trotz dieser erwarteten Schranken erforschen wir effiziente Lösungsansätze zum praktischen Zählen von Antworten, die auf zwei Grundprinzipien basieren: (1) Abstraktionen, die das Ziel der Vereinfachung und inkrementellen Lösung verfolgen; (2) Systematisches Über- und Unterzählen, um mittels kontinuierlicher Verbesserung bereits berechneter oberer und unterer Lösungsschranken das Herantasten an die Gesamtanzahl zu ermöglichen. Wir gehen davon aus, dass eine Kombination dieser Techniken wegweisend für die Erschließung neuer Anwendungen in der computationalen Biologie sein wird.