Neues DFG-Projekt „Foundations of work-efficient constant-time parallel dynamic and static algorithms“
Neuere Forschungen im Bereich der dynamischen Komplexitätstheorie haben viele algorithmische Probleme identifiziert, die durch dynamische parallele Algorithmen mit nur konstanter Zeit auf dem Parallel Random Access Model (PRAM), unabhängig von der Größe der Eingaben, bearbeitet werden können. So wurde zum Beispiel gezeigt, dass das Erreichbarkeitsproblem für gerichtete Graphen durch solche Algorithmen unter Einfügung und Löschung von Kanten aufrechterhalten werden kann. Diese Forschungen haben sich jedoch ausschließlich auf den Aspekt der konstanten Zeit konzentriert und andere Aspekte der Effizienz außer Acht gelassen, insbesondere den Arbeitsaufwand, d.h. die Gesamtzahl der Schritte, die über alle Prozessoren summiert werden. Infolgedessen ist der Arbeitsaufwand, den die in der Literatur beschriebenen Algorithmen erfordern, ein ernsthaftes Hindernis für ihre praktische Nützlichkeit.
Das Hauptziel dieses Projekts ist der Entwurf von arbeitseffizienten parallelen dynamische Algorithmen mit konstanter Laufzeit für wichtige algorithmische Probleme zu entwerfen und vielseitige algorithmische Techniken zu entwickeln. Ein eng damit verbundenes zusätzliches Ziel ist der Entwurf arbeitseffizienter paralleler statischer Algorithmen mit konstanter Zeit, insbesondere für Teilaufgaben dynamischer Algorithmen. In ergänzenden Untersuchungen wird versucht, Hindernisse für die Existenz und Arbeitseffizienz beider Arten von Algorithmen zu identifizieren und eine Sprache zu entwerfen, mit der solche dynamischen Algorithmen spezifiziert werden können.