Homogene Strukturen, Bedingungserfüllungsprobleme, und topologische Klone

• Antragsteller: Professor Dr. Manuel Bodirsky
• Fachliche Zuordnung: Mathematik ; Theoretische Informatik
• Förderung: Förderung von 2015 bis 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 280296726

Klone sind eine Verallgemeinerung von Gruppen, die in der universellen Algebra eine zentrale Bedeutung haben. Unlängst haben Klone zusätzlich in der theoretischen Informatik Bedeutung erlangt, da sie ein sehr mächtiges Werkzeug sind, um die Berechnungskomplexität von Bedingungserfüllungsproblemen (kurz "CSPs" von englisch "Constraint Satisfaction Problems") zu untersuchen. Um dieses mächtige Werkzeug auch für CSPs mit unendlichen Wertebereichen einsetzen zu können, betrachtet man Funktionsklone, die mit der Topologie der punktweisen Konvergenz ausgestattet sind. Damit werden Klone zu topologischen Klonen, ganz analog zu den topologischen Gruppen von Permutationsgruppen bezüglich der punktweisen Konvergenz. Wenn die Relationen des CSPs eine omega-kategorische Theorie bilden, so kann man zeigen, dass die Berechnungskomplexität des CSPs nur vom topologischen Polymorphismenklon dieser Relationen abhängt. Das betrifft insbesondere Relationen, die in homogenen Strukturen mit endlicher relationaler Signatur definierbar sind, und die entsprechende Klasse von CSPs umfasst eine Vielzahl an natürlichen Berechnungsproblemen, die in verschiedenen Gebieten der theoretischen Informatik studiert wurden. Eines der wichtigsten Hilfsmittel, um Polymorphismenklone von solchen Relationen zu untersuchen, ist Ramsey theorie. Das Ziel dieses Projektes ist, das Zusammenspiel von topologischen und algebraischen Eigenschaften von topologischen Klonen gerade im Hinblick auf die erwähnte Anwendung fuer CSPs zu untersuchen. Weiterhin möchten wir die Methoden aus der Ramseytheorie für diese Untersuchungen weiterentwickeln.

• DFG-Verfahren: Sachbeihilfen