Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung

01.09.2008 - 31.08.2012
Forschungsförderungsprojekt
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.

Personen

Projektleiter_in

Projektmitarbeiter_innen

Institut

Förderungsmittel

  • Fonds zur Förderung der wissenschaftlichen Forschung (FWF)

Forschungsschwerpunkte

  • Information and Communication Technology

Schlagwörter

DeutschEnglisch
Parameterized ComplexityParameterized Complexity
Fixed-parameter TractabilityFixed-parameter Tractability
Tree-widthTree-width
DatalogDatalog
Monadic Second-order logicMonadic Second-order logic

Externe Partner_innen

  • Universita degli Studi di Calabria
  • Oxford University Computing Laboratory