Repräsentationskomplexität in Algorithmen zum Aufzählen und Zählen

• Antragsteller: Professor Dr. Christoph Berkholz
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 414325841

Die Komplexitätsanalyse algorithmischer Fragestellungen ist ein zentrales Thema der theoretischen Informatik. So liefert die Komplexitätstheorie geeignete Werkzeuge, um mittels Reduktionen die Komplexität von Entscheidungs- und Zählproblemen in Abhängigkeit von der Eingabegröße und -struktur zu untersuchen. Das beantragte Projekt befasst sich mit der Komplexität algorithmischer Fragestellungen, die - im Gegensatz zu klassischen Entscheidungsproblemen - eine Ausgabe erzeugen. Insbesondere sollen Verfahren untersucht werden, die eine kompakte Repräsentation ihrer Ausgabe berechnen. Auf der einen Seite können solche Algorithmen deutlich schneller terminieren, als die Größe ihrer Ausgabe es vorgibt. Auf der anderen Seite erlauben geeignete kompakte Repräsentationen der Ausgabe sowohl eine speichereffiziente Darstellung als auch eine effiziente Weiterverarbeitung, wie beispielsweise das Bestimmen der Ausgabegröße oder das Aufzählen der Ausgabeelemente in kurzen Intervallen. Methoden zur kompakten Repräsentation wurden seit knapp zwanzig Jahren im Bereich "knowledge compilation" insbesondere für das Zählen und Aufzählen erfüllender Belegungen aussagenlogischer Formeln weiterentwickelt. Daran angelehnte Konzepte wurden in den letzten Jahren außerdem zur Entwicklung speicherplatzeffizienter Datenstrukturen in Constraint Solvern als auch bei der Entwicklung effizienter Mehrfach-Join Algorithmen verwendet. In diesem Projekt soll eine umfassende Theorie kompakter Repräsentationen für das Constraint Satisfaction Problem und für die Anfrageauswertung in relationalen oder probabilistischen Datenbanken entwickelt werden. Dabei sollen zum einen möglichst kompakte Repräsentationsformate entwickelt werden, die ein effizientes Weiterverarbeiten ermöglichen. Zum anderen sollen die Grenzen der effizienten Repräsentierbarkeit durch das Beweisen unterer Schranken an die Größe von Repräsentationen aufgezeigt werden. Im Bereich des Constraint Satisfaction Problems wollen wir die Struktur der Instanzen verstehen, die eine polynomiell große Repräsentation der (möglicherweise exponentiell großen) Lösungsmenge erlauben. Um die Grenze effizienter Repräsentationen auszuloten, werden wir geeignete Einschränkungen sowohl an die Constraintsprache als auch an die Struktur des Constraintnetzwerks betrachten. Im Bereich der Datenbanktheorie wollen wir Anfrageauswertungsalgorithmen entwickeln die, gegeben eine logische Formel aus einer bestimmten Anfragesprache und eine relationale oder probabilistische Datenbank, eine kompakte Repräsentation der Ergebnisrelation erzeugen. Auch hier wollen wir passende untere Schranken an die Größe von Repräsentationen beweisen. Ein weiteres Ziel ist das Entwickeln dynamischer Repräsentationen, die es nach einer Modifikation der Eingabe ermöglichen, die Repräsentation der geänderten Ausgabe effizient anzupassen.

• DFG-Verfahren: Emmy Noether-Nachwuchsgruppen