NW/1: Repräsentationskomplexität in Algorithmen zum Aufzählen und Zählen


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 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 polynominell 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.


Projektleitung
Berkholz, Christoph Dr. (Details) (Theoretische Informatik)

Mittelgeber
DFG: Nachwuchsgruppe

Laufzeit
Projektstart: 10/2019
Projektende: 09/2022

Forschungsbereiche
Informatik, Theoretische Informatik

Zuletzt aktualisiert 2023-26-04 um 06:30