Constraint Satisfaction Problems (CSPs) sind eine Klasse von Entscheidungsproblemen, die in vielen Bereichen der Informatik auftreten. Ein CSP wird durch eine relationale Struktur B über einer endlichen Signatur, dem sogenannten Template, parametrisiert. Die Eingabe des CSP von B sind eine Menge von Variablen sowie eine endliche Anzahl von Bedingungen ("constraints") über diesen Variablen. Das Problem ist, zu entscheiden, ob es Werte aus der Grundmenge von B gibt, die den Variablen so zugewiesen werden können, das alle Bedingungen gleichzeitig erfüllt sind. Dieser Ansatz kann verallgemeinert werden, um auch Optimierungsprobleme zu modellieren. In diesem Fall wird jede Relation von B durch eine Kostenfunktion ersetzt, und die Eingabe enthält zusätzlich einen Schwellenwert. Anstatt die Erfüllbarkeit zu entscheiden, wird entschieden, ob es eine Zuordnung von Werten zu Variablen gibt, so dass die Summe der Kosten durch den Schwellenwert begrenzt wird. Solche Probleme werden Valued CSPs (VCSPs) genannt. Es ist bekannt, dass die Komplexität von VCSPs über endlichen Grundmengen eine Dichotomie aufweist: Sie sind entweder in der Klasse P oder NP-vollständig. Viele natürlich auftretende Optimierungsprobleme, wie z.B. das Minimum-Feedback-Arc-Set-Problem oder das Min-Correlation-Clustering-Problem, können jedoch nicht durch eine Struktur mit endlicher Grundmenge modelliert werden.
Von Fortschritten in der Erforschung von CSPs über unendlichen Grundmengen motiviert, untersuchen wir VCSPs über unendlichen Grundmengen. Inspiriert durch die in der Fachwelt akzeptierten modelltheoretischen Einschränkungen für CSPs über unendlichen Grundmengen konzentrieren wir uns auf Templates mit oligomorpher Automorphismengruppe. Ziel des Projekts ist, die Komplexität relevanter Teilklassen solcher VCSPs zu klassifizieren, die algebraische Theorie von VCSPs zu erforschen, und dieses Wissen auf konkrete Probleme anzuwenden, die als VCSPs modelliert werden können. Als Beispiel seien hier Resilienzprobleme aus der Datenbanktheorie genannt. Um diese speziellen Probleme zu erforschen, kombinieren wir Methoden aus der Erforschung von VCSPs über endlichen Mengen mit dem modelltheoretischen Ansatz, der erfolgreich für CSPs über unendlichen Mengen genutzt wurde, und passen sie entsprechend an. So bedienen wir uns dabei einer Kombination von Gadget-Reduktionen für VCSPs, die auf den Konzepten der Expressibilität und pp-Konstruierbarkeit basieren, mit den Symmetrien der Templates, den sogenannten fraktionalen Polymorphismen.
VCSPs über unendlichen Mengen wurden bisher kaum erforscht. Daher eröffnet dieses Projekt neue Perspektiven im Bereich der Constraint Satisfaction Problems und der Berechnungskomplexität von Optimierungsproblemen. Wir erwarten, den algebraischen Ansatz zur Erforschung von VCSPs über unendlichen Mengen weiterzuentwickeln und das Verständnis für die Zusammenhänge zwischen den algebraischen Eigenschaften und der Komplexität dieser Probleme deutlich zu verbessern. Dies kann zu einem systematischen Ansatz für die Komplexitätsklassifizierung ganzer Klassen von Optimierungsproblemen führen, die bislang sehr schwierig zu erforschen sind.
