Perspektiven auf die dynamische Komplexitätstheorie

• Antragsteller: Professor Dr. Thomas Zeume
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 532727578

Sehr schnelle, parallele, dynamische Algorithmen sind in den letzten Jahrzehnten aus der Perspektive der dynamischen Komplexitätstheorie intensiv erforscht worden. Solche Algorithmen sind überraschend mächtig: Unter anderem wurde kürzlich gezeigt, dass Erreichbarkeit in gerichteten Graphen in konstanter paralleler Zeit dynamisch berechnet werden kann. Während in den letzten Jahren erhebliche Fortschritte beim Entwurf von Algorithmen erzielt wurden, lag der Schwerpunkt in weit geringerem Maße auf strukturellen Ergebnissen. Das Ziel dieses Projekts ist eine systematische Untersuchung komplexitätstheoretischer Fragen für sehr schnelle, parallele, dynamische Algorithmen. Der Schwerpunkt liegt dabei auf der Erforschung von (A) Grenzen der Mächtigkeit sehr schneller, paralleler, dynamischer Algorithmen; (B) die feinkörnige Struktur von kleinen, parallelen, dynamischen Komplexitätsklassen; und (C) Verbindungen zwischen verschiedenen dynamischen, parallelen Berechnungsmodellen sowie anderen Bereichen der theoretischen Informatik.

• DFG-Verfahren: Sachbeihilfen