Komplexität von Optimierung: VCSPs auf unendlichen Mengen

Bedingungserfüllbarkeitsprobleme tauchen ganz natürlich im täglichen Leben auf. Typische Beispiele sind Terminplanungsprobleme wie die Suche nach einem geeigneten Zeitfenster für eine Besprechung. Oftmals können nicht alle Bedingungen erfüllt werden, z.B. kann nicht jeder an der Besprechung teilnehmen, da die Zeitpläne der Teilnehmer inkompatibel sind. Dies motiviert eine natürliche Optimierungsaufgabe: man ordnet den verschiedenen Bedingungen Kosten zu, welche anfallen, wenn die Bedingung nicht erfüllt wird, und versucht, die Summe dieser Kosten zu minimieren. Beispielsweise könnte eine unvermeidbare Bedingung an die Besprechung sein, dass sie an einem Werktag zwischen 8 und 16 Uhr stattfinden muss; in diesem Fall betrachten wir die Kosten dieser Bedingung als unendlich. Andererseits könnten wir einigen Personen erlauben, nicht an der Besprechung teilzunehmen, und der Bedingung der Teilnahme dieser Personen jeweils Kosten von 1 zuordnen; dies bedeutet, dass wir die Anzahl der Abwesenheiten minimieren. Bedingungserfüllbarkeitsprobleme dieser Art und ihre Optimierungsvariante können durch die mathematische Theorie der Valued-Constraint-Satisfaction- Problems modelliert werden, bei denen man ganz allgemein versucht, Variablen Elemente aus einer festen Grundmenge (z.B. mögliche Zeitfenster in einer Arbeitswoche) zuzuordnen und dabei die Kosten dieser Zuordnung zu minimieren. In den letzten Jahren wurde die Berechnungskomplexität von Bedingungserfüllbarkeitsproblemen und ihren Varianten eingehend untersucht. Diese Forschung führte zur Entwicklung algebraischer Eigenschaften, die auf elegante Weise die Grenze zwischen effizient lösbaren und schweren Problemen beschreiben. Der algebraische Ansatz ebnete den Weg zu einer vollständigen Komplexitätsklassifizierung fürValued-Constraint-Satisfaction-Problems überendlichen Grundmengen. Viele konkrete Probleme, z.B. Terminplanungs- oder Clustering-Probleme, können jedoch nicht über endlichen Grundmengen modelliert werden. Aus diesem Grund liegt der Schwerpunkt dieses Projekts auf Problemen über unendlichen Grundmengen. Solche Probleme sind bisher kaum untersucht worden, und eine geeignete algebraische Theorie muss noch entwickelt werden. Wir beschränken uns auf eine Unterklasse von Problemen, die trotz der unendlichen Grundmenge Problemen mit endlicher Grundmenge in gewissem Sinne ähnlich sind. Daher ist eine Anpassung der algebraischen Methoden, die für endliche Vorlagen fruchtbar waren, erfolgversprechend. Wir gehen davon aus, dass dieses Projekt den Horizont in der Erforschung von Constraint-Satisfaction-Problems erweitern und das Verständnis für die mathematische Struktur von Valued-Constraint-Satisfaction- Problems erheblich verbessern wird.