Algorithmische Probleme in der Gruppentheorie

• Antragsteller: Professor Dr. Markus Lohrey; Dr. Armin Weiß
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2016 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 288360912

Die Hauptziele des Projekts haben sich gegenüber dem Erstantrag nicht verändert:- Wir wollen die Komplexität algorithmischer Probleme in der Gruppentheorie (insbesondere Wortprobleme und Konjugationsprobleme) mittels kleiner Komplexitätsklassen aus der Schaltkreis- und Platzkomplexität möglichst genau lokalisieren. Diesbezüglich konnten wir in den letzten Jahren große Fortschritte erzielen.- Langfristig wollen wir das Gebiet der algorithmischen Gruppentheorie in Deutschland etablieren. Erste Erfolge können wir hier bereits verbuchen.Bezüglich des ersten Punkts hat sich der Fokus im Neuantrag etwas verschoben: Während in der ersten Projektphase der Schwerpunkt primär auf Graphprodukten und Fundamentalgruppen von Gruppengraphen (mit verallgemeinerten Baumslag-Solitar-Gruppen als wichtiger Spezialfall) lag, wollen wir in den nächsten drei Jahren unsere Untersuchungen auf weitere wichtige Gruppenklassen wie etwa Automatengruppen und meta-abelsche Gruppen ausdehnen. Außerdem wollen wir auch Probleme, deren Komplexität in mächtigeren Komplexitätsklassen lokalisiert ist,in unsere Betrachtungen einschließen. Dies umfasst diskrete Optimierungsprobleme, Lösung von Wortgleichungen und komprimierte Wortprobleme. In der ersten Projektphase konnten wir neue Techniken zur Lösung dieser Probleme entwickeln. Wir möchten die Anwendbarkeit dieser Techniken in der zweiten Projektphase weiter untersuchen.

• DFG-Verfahren: Sachbeihilfen