Metafragen in Bedingungserfüllung auf unendlicher Grundmenge

In der theoretischen Informatik bieten Constraint Satisfaction Problems (CSPs) eine Abstraktion des Erfüllbarkeitsproblems für Gleichungssysteme. Gegeben eine endliche Menge von Variablen und eine endliche Menge von Nebenbedingungen über diesen Variablen, es wird eine Belegung der Variablen mit Werten aus einem festen Definitionsbereich gesucht, die alle Nebenbedingungen gleichzeitig erfüllt. Zum Beispiel könnten die Nebenbedingungen lineare Gleichungen mit rationalen Koeffizienten sein und der Definitionsbereich die Menge der rationalen Zahlen; dann besteht die Aufgabe darin, ihre Lösbarkeit im üblichen Sinn zu entscheiden. Ein CSP heißt endlich, wenn der Definitionsbereich endlich ist, und unendlich sonst. Ein zentrales Thema ist die Frage, welche CSPs effizient lösbar sind und welche rechnerisch schwierig. In unserem Beispiel lassen sich lineare Gleichungssysteme über den rationalen Zahlen effizient mit dem Gaußschen Eliminationsverfahren lösen, nicht aber über den natürlichen Zahlen. Ein effizienter Algorithmus dort würde weitreichende Folgen haben, etwa zur Lösung des P=NP-Problems führen. Um die Komplexität von CSPs systematisch zu untersuchen, war es notwendig, weit über den ursprünglichen formalen Rahmen dieser Probleme hinauszugehen. Der erste wesentliche Schritt war die Erkenntnis, dass die zugrunde liegende algebraische Struktur entscheidend für die Klassifikation ihrer Komplexität ist; diese fundamentale Einsicht reichte aus, um alle CSPs mit zweielementigem Definitionsbereich vollständig zu klassifizieren. Eine vollständige Komplexitätsklassifikation aller endlichen CSPs gelang erst Jahrzehnte später durch eine Kombination tiefgreifender Resultate aus der Strukturtheorie endlicher Algebren. Sie zeigt: Jedes endliche CSP ist entweder effizient lösbar oder so schwierig wie das schwierigste Problem dieser Klasse. Der Grad an Allgemeinheit, den der CSP-Rahmen bei unendlichen Definitionsbereichen ermöglicht, ist enorm. Aus diesem Grund werden CSPs mit unendlichem Definitionsbereich meist nur unter zusätzlichen strukturellen Einschränkungen untersucht. Ein aktives Forschungsprogramm beschäftigt sich derzeit mit der Erweiterung des algebraischen Ansatzes auf CSPs über unendlichen Definitionsbereichen sowie mit einer Vermutung, die den Dichotomiesatz für endliche CSPs auf den unendlichen Fall verallgemeinern soll. Die genaue Verbindung zwischen der algebraischen Struktur unendlicher CSPs und ihren algorithmischen Eigenschaften ist jedoch bislang nur unzureichend verstanden. Ziel des Projekts ist es, das algorithmische Verhalten der Vermutung im unendlichen Fall besser zu verstehen, mögliche Vereinfachungen zu identifizieren und ihre Relevanz für andere Teilgebiete der theoretischen Informatik zu untersuchen. Dazu werden u. a. vergleichende Studien mit Ergebnissen aus der Datenbanktheorie, der strukturellen Ramsey-Theorie und der topologischen Dynamik durchgeführt sowie Metafragen rund um die Vermutung analysiert.