Eine Algebraische Theorie für Promise Constraint Satisfaction Probleme

Heuristisch ausgedrückt ist die Komplexität eines Berechnungsproblemes ein Maß dafür, wie schwierig es für einen Computer ist, es zu lösen. Nachdem Computer heutzutage eine große Rolle in unserem Leben spielen, ist eine der großen Fragen unserer Zeit, welche Berechnungsprobleme von Computern ausreichend effizient gelöst werden können; sie findet beispielsweise in der künstlichen Intelligenz Anwendungen. Das Ziel dieses Projektes ist die Untersuchung der Komplexität von Promise Constraint Satisfaction Problemen (PCSP). Diese sind eine Verallgemeinerung von Constraint Satisfaction Problemen (CSP). Informell kann man sagen, daß eine Instanz eines CSP oder eines PCSP ein Rätsel von der Bauart eines Sudoku ist - es sind bestimmten Variablen Werte aus einer fixen Wertemenge so zuzuordnen, daß bestimmte Einschränkungen eingehalten werden. Dabei geht es allerdings nur darum festzustellen, ob eine Lösung existiert oder nicht, und nicht darum, tatsächlich eine Lösung zu präsentieren. Der Unterschied zwischen CSP und PCSP ist, daß bei letzteren zwei mögliche Wertemengen betrachtet werden, wovon eine restriktiver ist; die Frage ist, ob eine Lösung in der restriktiveren Wertemenge existiert, oder nicht einmal eine Lösung in der weniger restriktiven. Unlängst wurde im Falle von CSP ein großer Durchbruch erreicht, und die Komplexität von allen CSP mit endlichen Wertemengen klassifiziert. Dabei wurde die Erkenntnis verwendet, daß die Komplexität in bestimmtenalgebraischenObjekten kodiert ist, die Polymorphismenklone heißen. Die für diese Objekte entwickelte algebraische Theorie ermöglichte dann den Beweis der genannten Klassifikation. Obwohl sich diese Theorie nicht direkt auf PCSP übertragen lässt, ist bekannt, daß die Komplexität in anderen algebraischen Objekten kodiert ist, die Polymorphismenklonoide genannt werden. Das Entwickeln einer entsprechenden algebraischen Theorie ist das Ziel dieses Projektes. Dabei werden wir, im Gegensatz zu anderen Projekten, besonderen Wert auf PCSPs mit unendlichen Wertemengen legen. Diese breitere Perspektive vereint Methoden mehrerer mathematischer Disziplinen, insbesondere der mathematischen Logik, der Topologie, und der Kombinatorik, die in dieser Form für endliche Wertemengen keine Rolle spielen. Wir gehen davon aus, daß wir durch dieses Projekt Einsicht in das grundlegende Wesen von Berechnungsproblemen gewinnen werden.

Die Komplexität eines (rechnerischen) Problems kann als ein Maß dafür sein, wie einfach oder schwierig es ist, das besagte Problem zu lösen. In der Praxis wollen wir wissen, wie viel Zeit oder andere Computerressourcen eine solche Berechnung benötigt werden und wie sich dieser Betrag ändert, wenn die Eingabegröße vergrößert wird. Wenn eine Internet-Suchmaschine beispielsweise $10$-mal mehr Websites als bisher verarbeiten muss, sind die dafür benötigten Ressourcen $10$-mal höher, $100$-mal höher, oder ist das Wachstum exponentiell. Die Antwort auf diese Frage kann tiefgreifende Auswirkungen darauf haben, was rechnerisch machbar ist. Das Ziel dieses Projekts war die Untersuchung der Komplexität einer bestimmten wichtigen Klasse von Problemen, die als Promise Constraint Satisfaction Problems oder kurz PCSP. PCSP ist eine geeignete Verallgemeinerung einer anderen gut untersuchten Klasse von Probleme - Constraint Satisfaction Problems, kurz CSP. In den letzten paar Jahren wurde ein Durchbruch bei der Untersuchung von CSP erzielt worden, nämlich die Komplexität der CSP über eine große und natürliche Klasse wurde klassifiziert. Die wesentliche Beobachtung für diese Klassifizierung war die Tatsache, dass die Komplexität eines CSP nur von einem bestimmten algebraischen Objekt abhängt, das mit ihm assoziiert ist, dem sogenannten Polymorphism Clone. In der Folge wurde eine fruchtbare algebraische Theorie entwickelt, die schließlich zum Beweis der oben genannten Klassifikation führte. Es wurde bereits festgestellt, dass im Fall von PCSP auch ein zugehöriges algebraisches Objekt existiert, das Polymorphism Clonoid, das die Komplexität kodiert. Von besonderem Interesse in diesem Projekt war der Fall, dass die zugrundeliegenden Strukturen die ein Promise Constraint Satisfaction Problem definieren, unendlich sind aber wohlbehalten. In solchen Fällen kann man neben der algebraischen Struktur eine zusätzliche topologische Struktur verwenden, die sich im Bereich der CSP als nützlich erwiesen hat. Die wichtigsten Forschungsergebnisse des Projekts unterstreichen die Bedeutung der Topologie und ihre Wechselwirkungen mit der algebraischen Struktur. Zum einen zeigen wir, dass es für bestimmte gut untersuchte Strukturen eine eindeutige Topologie gibt, die die mit der algebraischen Struktur des Polymorphism Clone kompatibel ist. Andererseits zeigen wir, dass ein neueres Ergebnis über die Relevanz der Topologie (in einer Dichotomie Vermutung für Constraint Satisfaction Problems mit unendlicher Domäne) auch für CSP-Templates gelten, das heißt für Strukturen, die auf sinnvolle Weise CSP ergeben.