Grundlagen der algorithmischen Stabilitätstheorie

• Antragsteller: Professor Dr. Sebastian Siebertz
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 444419611

Die Logik ist traditionell sehr eng mit der Informatik verbunden. Klassische Beispiele für diese Verbindung findet man etwa in der Berechenbarkeitstheorie, in der Theorie der regulären Sprachen oder in der deskriptiven Komplexitätstheorie. Eine aktuelle Anwendung findet die Logik in der Formulierung von algorithmischen Meta-Sätzen. Ein algorithmischer Meta-Satz beschreibt algorithmische Techniken, die nicht nur für einzelne Probleme, sondern für ganze Klassen von Problemen anwendbar sind. Diese Problemklassen werden oft mit Hilfe von Logik spezifiziert. Ein prototypisches Beispiel ist Coucelles Satz, der besagt, dass jede Eigenschaft von Graphen, die in der monadischen Prädikatenlogik zweiter Stufe (MSO) definierbar ist, auf jeder Klasse von Graphen mit beschränkter Baumweite in Linearzeit entschieden werden kann. Ein weiteres Ergebnis besagt, dass jede Eigenschaft von Graphen, die in der Prädikatenlogik erster Stufe (FO) definiert werden kann, auf jeder nowhere dense Klasse von Graphen in fast linearer Zeit entschieden werden kann. Die beiden obigen Ergebnisse können unter Standardannahmen aus der Komplexitätstheorie nicht auf allgemeinere monotone Graphklassen erweitert werden. Hier wird eine Klasse als monoton bezeichnet, wenn sie unter der Subgraphrelation abgeschlossen ist. Die Klassifikation von monotonen Graphklassen, auf denen MSO- und FO-Eigenschaften effizient ausgewertet werden können, ist also im Wesentlichen vollständig abgeschlossen. Das Ziel des hier vorgestellten Projekts ist die Erforschung der algorithmischen Theorie strukturierter, nicht-monotoner Graphklassen. Insbesondere soll die Existenz algorithmischer Meta-Sätze für die Prädikatenlogik erster Stufe auf solchen Klassen untersucht werden. Methodisch sollen Verbindungen zwischen Graphtheorie, Algorithmik und klassischer Modelltheorie der Prädikatenlogik, insbesondere im Teilgebiet der Stabilitätstheorie (stability theory oder classification theory), benutzt werden. In aktuellen Vorarbeiten werden diese Bereiche erfolgreich verknüpft. So konnten etwa die zentralen Eigenschaften der Stabilität (stability) und Abhängigkeit (dependence, non-independence (NIP)) genutzt werden um effiziente Algorithmen auf strukturierten Graphklassen zu entwickeln. Im Projekt sollen die Grundlagen einer algorithmischen Stabilitätstheorie geschaffen werden und ihre Anwendbarkeit in der endlichen Kombinatorik und Graphtheorie demonstriert werden. Anwendungen wird die Theorie in der theoretischen Informatik, insbesondere in der parametrisierten Komplexitätstheorie und in der Theorie der Approximationsalgorithmen, sowie in der Graphtheorie und Logik finden.

• DFG-Verfahren: Sachbeihilfen