Parameterisierte Kompilierung

Wissenskompilierung ist ein wichtiger Ansatz zur Lösung rechnerisch schwieriger Probleme. Dieser Ansatz wurde in den frühen 1990er Jahren eingeführt und ist seither ein sehr aktives Forschungsgebiet. Wissenskompilierung spaltet den Lösungsprozess in zwei Phasen: in einer ersten Phase, der Kompilierungsphase, werden die Eingabedaten in eine neue Darstellung übergeführt, die dann in einer zweiten Phase dazu verwendet werden, um eine große Anzahl von einzelnen Abfragen effizient auszuführen. Im Idealfall soll die Kompilierungsphase nur eine polynomielle Vergrößerung der Eingabedaten bewirken. Die systematische Erforschung der Kompilierbarkeit wichtiger Probleme, zeigt, dass nur sehr wenige praxisrelevante Probleme eine solche Kompilierung mit polynomiellem Platzbedarf erlauben. Für viele wichtige Problem kann die klassischen Theorie der Wissenskompilierung daher keine guten obere Schranken für den Kompilierungsplatz geben. Das Forschungsziel ist strukturelle Aspekte der Eingabedaten für die Wissenskompilierung auszunützen und damit den klassischen Ansatzes zur Wissenskompilierung zu erweitern und zu verfeinern. Um dieses Ziel zu erreichen, werden wir Methoden und Konzepte der parametrisierten Komplexität verwenden. Parametrisierten Komplexität ist eine wichtige Forschungsrichtung aus dem Gebiet der Algorithmen und Komplexitätstheorie, die den klassischen Begriff der Berechenbarkeit in Polynomialzeit erweitert, in dem sie verschiedene strukturelle Eigenschaften der Eingabedaten (wie Baumweite oder den Grad der Zyklizität) ausnutzt, und damit mächtige algorithmische Methoden zur Verfügung stellt. Für die Wissenskompilierung ermöglicht die parameterisierte Analyse neue positive Resultate in Form von oberen Schranken zu Kompilierungsplatz und Kompilierungszeit für Probleme, die im klassischen Sinne nicht kompilierbar sind. Die geplante Forschungsarbeit wird geleitet durch die Analyse von konkreten Kompilierungsproblemen aus den Bereichen des abduktiven Schließens, des logischen Programmierens, der abstrakten Argumentation, und des aussagenlogischen Planens. Die Erkenntnisse und Resultate einzelnen Kompilierungsproblemen werden zu einem allgemeinen theoretischen Fundament zusammengefasst, mit dem allgemeine Methoden zur Erstellung von oberen und unteren Platz- und Zeitschranken für die Wissenskompilierung erstellt werden können. Ein weiteres Ziel ist es, empirisch zu untersuchen, wie einzelne Parameter in realistischen Problemeingaben verteilt sind.

Wissenskompilierung ist ein wichtiger Ansatz zur Lösung rechnerisch schwieriger Probleme. Dieser Ansatz wurde in den frühen 1990er Jahren eingeführt und ist seither ein sehr aktives Forschungsgebiet. Wissenskompilierung spaltet den Lösungsprozess in zwei Phasen: in einer ersten Phase, der Kompilierungsphase, werden die Eingabedaten in eine neue Darstellung übergeführt, die dann in einer zweiten Phase dazu verwendet werden, um eine große Anzahl von einzelnen Abfragen effizient auszuführen. Im Idealfall soll die Kompilierungsphase nur eine polynomielle Vergrößerung der Eingabedaten bewirken. Die systematische Erforschung der Kompilierbarkeit wichtiger Probleme, zeigt, dass nur sehr wenige praxisrelevante Probleme eine solche Kompilierung mit polynomiellem Platzbedarf erlauben. Für viele wichtige Probleme kann die klassischen Theorie der Wissenskompilierung daher keine guten obere Schranken für den Kompilierungsplatz geben. Das Forschungsziel dieses Projektes war es, strukturelle Aspekte der Eingabedaten für die Wissenskompilierung auszunützen und damit den klassischen Ansatzes zur Wissenskompilierung zu erweitern und zu verfeinern. Dies ist uns auch gelungen. Zum einen haben wir eine Verbindung zwischen Wissenskompilierung und der parametrisierten Komplexitätstheorieentwickelt, dieuns erlaubt, negative Komplexitätsergebnisse zu relativieren, in dem wir zusätzliche Eigenschaften des zu kompilierenden Wissens auszunutzen. Ein grundlegendes Beispiel für solch ein negatives Resultat in der Wissenskompilierung ist, dass sich aussagenlogische Theorien in konjuntiver Normalform nicht in Polynomialplatz kompilieren lassen. Wir konnten verschiedenen syntaktische Eigenschaften solcher Theorien aber auch von Booleschen Funktionen aufzeigen, die eine Kompilierung mit wenig Platzbedarf erlauben. Weiters haben wir zur Theorie der handhabbaren Repräsentationen beigetragen, die auf Arbeiten von Darwiche und Marquis und deren Wissenskompilierungskarte aufbaut. Hier haben wir den Stand der Technik erheblich erweitert, u.A. mithilfe einer neuen Verbindung zwischen Wissenskompilierung und Kommunikationskomplexität.