Faktorisierung in endlichen Gruppen

• Antragsteller: Professor Dr. Markus Lohrey
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 544679539

Der algorithmische Zweig der Theorie endlicher Gruppen hat zahlreiche Anwendungen in der Mathematik und Informatik, z.B. in der abstrakten Algebra, Automatentheorie, Komplexitätstheorie, Quantencomputing, Kryptographie und Algorithmen für Graphenisomorphie. Viele algorithmische Probleme in diesen Anwendungsbereichen fragen nach der Existenz einer bestimmten Faktorisierung eines Gruppenelements. Ein berühmtes Beispiel für ein Faktorisierungsproblem ist das Zugehörigkeitsproblem für eine endliche Gruppe G. Hier wird gefragt, ob ein gegebenes Element g aus G sich als Produkt von weiteren gegebenen Elementen aus G schreiben lässt. Andere Faktorisierungsprobleme entstehen durch weitere Einschränkungen der erlaubten Produktdarstellungen von g. Solche Einschränkungen können mit sprachtheoretischen Mitteln, wie z.B. endlichen Automaten oder kontextfreien Grammatiken formuliert werden. In dem Projekt wollen wir Faktorisierungsprobleme für endliche Gruppen systematisch aus verschiedenen Blickwinkeln betrachten: • Wir werden Faktorisierungsprobleme aus verschiedenen algorithmischen Perspektiven untersuchen: Worst-Case-Komplexität, parametrisierte Komplexität, Aufzählungskomplexität, Zählkomplexität und Kompaktheit von Beschreibungen. • Wir wollen hauptsächlich an Faktorisierungsproblemen für Permutationsgruppen arbeiten. Gelegentlich werden wir auch Black-Box-Gruppen berücksichtigen. Dabei werden wir auch algebraische und kombinatorische Unterklassen von Gruppen untersuchen, die zu besseren algorithmischen Ergebnissen führen könnten. Natürliche Kandidaten sind abelsche Gruppen, nilpotente Gruppen, auflösbare Gruppen oder transitive Permutationsgruppen. • Um die Eigenschaften der gewünschten Faktorisierung von Gruppenelementen zu spezifizieren, bieten sich automatentheoretische Konzepte an. In unserer bisherigen Arbeit haben sich dafür endliche Automaten und kontextfreie Grammatiken (sowie deren Unterklassen) als nützlich erwiesen und sollen deshalb in dem Projekt zum Einsatz kommen. Wir planen, einige unserer Algorithmen zu implementieren. Darüber hinaus wollen wir für komplexitätstheoretisch schwierige Probleme die Anwendbarkeit moderner SAT- und QBF-Solver-Technologien testen.

• DFG-Verfahren: Sachbeihilfen