Überwindung der Nichthandbarkeit im Compilation Map

In der Informatik kennt man verschiedene Datenstrukturen zur Darstellung von Boole`schen Funktionen, und je nach Anwendung sind unterschiedliche Darstellungen von Vorteil. Der Forschungszweig der "Knowledge Compilation" beschäftigt sich mit der Übersetzung zwischen diesen Darstellungen. Das "Kompilieren" einer Funktion bezeichnet den (potentiell zeitaufwändigen) Aufbau einer solchen Datenstruktur, die ein schnelles Auswerten der Funktion ermöglicht. Eine Klasse von Anfragen ist "effizient" für eine Datenstruktur, wenn es einen Algorithmus gibt, der sie schnell (in polynomieller Zeit) beantworten kann, wenn ihm diese Datenstruktur zur Verfügung steht. Die sogenannte "Knowledge Compilation Map" bietet eine Übersicht über häufig verwendete Datenstrukturen und deren effiziente Anfragen. Wichtige Kriterien, anhand derer Darstellungen von Funktionen verglichen werden können, sind deren Speichereffizienz, sowie der Umfang der Anfragen, die sie effizient beantworten können. Jede Kombination aus Datenstruktur und Anfrage kann demnach als "effizient" oder "ineffizient" eingestuft werden. Für eine Reihe von Datenstrukturen sind praxistaugliche Compiler entwicklet worden. Ziel des vorliegenden Projekts sind Methoden zur Beantwortung von Anfragen, die für die entsprechenden Datenstrukturen eigentlich "ineffizient" sind. Wir wollen zeigen, dass das Kompilieren die einfachere Beantwortung solcher Anfragen ermöglicht, selbst wenn sie nicht im engeren Sinn "effizient" werden. Ein Forschungsschwerpunkt es Projekts ist die Entwicklung von "parametrisierten" Ansätzen. Das umfasst einerseits die Entwicklung von Prozeduren, die für Datenstrukturen effizient sind, solange Parameter, die sie charakterisieren, klein genug sind. Andererseits können auch selbst Anfragen durch Parameter charakterisiert werden, deren Einschränkung ihre effiziente Beantwortung ermöglicht. Demnach kann Parametrisierung zu Methoden führen, die die effiziente Beantwortung einer Teilklasse von Anfragen erlauben. Eine weitere Forschungsrichtung ist die approximierte Beantwortung von Anfragen. Wenn eine Anfrage nicht effizient beantwortet werden kann, ist es häufig dennoch möglich, eine Antwort zu geben, die nahe an der korrekten Antwort liegt. Bislang ist Approximation nur als Eigenschaft des Kompilierens untersuchen worden, mit dem Ziel, die Größe der erzeugten Datenstruktur auf Kosten kleiner Fehler zu reduzieren. Stattdessen wollen wir Verfahren entwickeln, die exaktes Kompilieren mit approximativer Beantwortung von Anfragen kombiniert.

Das Hauptziel des Projekts bestand darin, schwer zu lösende Probleme zu untersuchen und Situationen zu finden, in denen diese Schwere überwunden werden kann. Unser wichtigster Beitrag ist die Entdeckung effizienter Algorithmen zur Lösung schwer zu lösender quantitativer Probleme auf eine approximative, aber dennoch rigorose Weise. Wir haben uns mit Problemen befasst, bei denen es darum geht, verschiedene Objekte oder Lösungen über einer bestimmten Datenstruktur zu zählen. Wir haben uns mit schwierigen Problemen beschäftigt, in dem Sinne, dass es viele zu zählende Lösungen geben kann und es wahrscheinlich keine Lösungsmethode gibt, die deutlich besser ist als eine aufwendige Brute-Force-Aufzählung aller möglichen Lösungen. Wir haben mehrere solcher Zählprobleme über grundlegende Datenstrukturen (zum Beispiel nicht-deterministische Automaten oder kontextfreie Grammatiken) untersucht und gezeigt, dass diese Probleme zwar für *exaktes* zählen schwer sind, für die aber effizientes *approximatives* Zählen möglich ist. Unsere wichtigste Errungenschaft ist die Entwicklung effizienter Polynomialzeitalgorithmen, die eine Approximation der tatsächlichen Anzahl von Lösungen liefern, wobei strenge Garantien für die Qualität der Approximation gegeben sind: Das Verhältnis zwischen der approximativen und der tatsächlichen Anzahl ist kontrolliert und kann beliebig nahe an 1 gebracht werden, und die Fehlerwahrscheinlichkeit kann verschwindend gering gemacht werden.