Oligomorphe Klone: CSPs über das Unendliche verstehen

Ein Klon ist eine Menge endlichstelliger Funktionen von einer Menge in sich selbst, welche unter Komposition abgeschlossen ist und welche alle Projektionen enthält. Klone treten in zweierlei Form auf: die Termoperationen einer Algebra bilden den sogenannten Termklon dieser Algebra (tatsächlich sind alle Klone von dieser Form); die Menge jener endlichstelligen Funktionen auf einer Menge, welche eine bestimmte relationale Struktur auf dieser Menge erhalten, bilden den sogenannten Polymorphismenklon dieser Struktur (nur die topologisch abgeschlossenen Klone sind von dieser Form). Die erste Quelle von Klonen erklärt ihre wichtige Rolle in der universellen Algebra, denn viele Eigenschaften von Algebren, beispielsweise ihre Unteralgebren und Kongruenzen, hängen nur vom Termklon der Algebra ab. Die letztere Quelle verbindet Klone mit relationalen Strukturen, und insbesondere mit gewissen Fragen der Komplexitätstheorie. Dieses Projekt hat das Studium von Klonen auf einer abzählbar unendlichen Menge und ihre Anwendungen in der Komplexitätstheorie zum Ziel. Während das Studium aller Klone all solcher Klone wegen der zu großen Allgemeinheit dieser Objekte wenig aussichtsreich ist, konnten unlängst viele Ergebnisse zu Klonen, welche hinreichend viel Struktur aufweisen, erzielt werden. In diesem Projekt interessieren wir uns für Klone, welche eine reiche Permutationsgruppe enthalten. Eine Permutationsgruppe, welche auf einer abzählbaren Menge D agiert, ist oligomorph, wenn ihre natürliche Aktion auf jeder endlichen Potenz von D nur endlich viele Bahnen hat. Klone, welche eine oligomorphe Permutationsgruppe enthalten, heißen ebenfalls oligomorph, und teilen bestimmte Eigenschaften mit Klonen auf endlicher Grundmenge. So läßt sich ein Satz von Birkhoff über endliche Klone auf oligmorphe Klone verallgemeinern; außerdem kodieren oligomorphe Klone die Komplexität bestimmter Berechnungprobleme, sogenannter constraint satisfaction problems (CSPs), und spielen eine wesentliche Rolle in der Erforschung solcher Probleme mit Hilfe der Algebra. Ein Beispiel von Berechungsproblemen, welche mittels oligomorpher Klone modelliert werden können, sind Graph-SAT-Probleme: dabei besteht eine Instanz des Problems aus einer endlichen Menge von Variablen, sowie Aussagen über diese Variablen in der Sprache der Graphen, wobei die Aussagen einer festen endlichen Menge S von möglichen Aussagen entstammen. Die Frage ist, ob man den Variablen Knoten in einem endlichen Graphen so zuordnen kann, daß die Aussagen über sie wahr werden. Mit den Methoden dieses Projektes läßt sich zeigen, dass das Graph-SAT-Problem für jede Aussagenmenge S entweder in P oder NP-vollständig ist. Während es in diesem Projekt hauptsächlich um universelle Algebra und CSPs geht, beinhalten die Methoden Konzepte verschiedener Gebiete der Mathematik, insbesondere homogene Strukturen, Struktursätze der Ramsey-Theorie, und topologische Gruppen.

Bedingungserfüllungsprobleme (CSPs) sind Berechnungsprobleme, bei denen zu gegebenen Variablen und Bedingungen zu den Variablen entschieden werden soll, ob den Variablen Werte so zugeordnet werden können, daß alle Bedingungen erfüllt sind. Ein Beispiel sind Gleichungen, in denen Variablen durch Multiplikation und Addition verknüpft sind; die Frage ist, ob die Gleichungen eine Lösung in den natürlichen Zahlen besitzen. Ein weiteres Beispiel sind logische Ausdrücke, in denen Variablen durch die logischen Verknüpfungen UND, ODER, und NEGATION kombiniert sind, und wo entschieden werden soll, ob man den Variablen die Wahrheitswerte WAHR oder FALSCH so zuordnen kann, daß der ganze Ausdruck WAHR wird. Ein drittes Beispiel sind Punkte, von denen manche verbunden sind, und wo man feststellen soll, ob die Punkte so in zwei Klassen aufgeteilt werden können, daß keine Verbindung innerhalb einer der beiden Klassen besteht (die Punkte werden hier als Variablen betrachtet, deren mögliche Werte die zwei Klassen sind). Manche CSPs können von einem Computer gelöst werden, andere nicht; von den oben genannten Beispielen ist dies genau für das zweite und das dritte der Fall. Auch wenn ein CSP von einem Computer gelöst werden kann, kann es dennoch so kompliziert sein, daß die Lösung im Allgemeinen nicht innerhalb vernünftiger Zeit gefunden wird. In diesem Projekt wird "in vernünftiger Zeit" mit "in polynomieller Zeit in der Größe einer Instanz des Problems" gleichgesetzt. Die Klasse aller Berechnungsprobleme, welche in vernünftiger Zeit gelöst werden können, wird mit P bezeichnet; das obige Beispiel der Klasseneinteilung von Punkten ist ein Beispiel für ein Problem in P. Andererseits wird angenommen, daß das genannte Problem der logischen Ausdrücke nicht in P liegt (diese Frage gehört zu den bekanntesten offenen Problemen der Mathematik). Berechnungsprobleme, die mindestens so schwer zu lösen sind wie das Problem der logischen Ausdrücke, heißen NP-schwer. Eine Vermutung besagt, daß eine bestimmte Klasse von CSPs eine sogenannte Komplexitätsdichotomie aufweist: alle Probleme dieser Klasse liegen entweder in P, oder sind NP-schwer; das heißt, es gibt laut der Vermutung innerhalb dieser Klasse keine CSPs, deren Komplexität schwerer als P, aber leichter als NP-schwer ist. Ziel dieses Projektes war es, diese Vermutung für bestimmte Teilklassen zu verifizieren, und jene CSPs, welche laut der Vermutung in P liegen, zu beschreiben. Es konnte bewiesen werden, daß die Vermutung für alle CSPs, bei denen es um bestimmte Eigenschaften von Ordnungen geht, gilt. Weiters wurde bewiesen, daß jene CSPs, die laut der Vermutung in P liegen, durch eine bestimmte Art von Symmetrie beschrieben werden können, und zwar durch eine konkrete Gleichung: u(s(x,y,x,z,y,z))=v(s(y,x,z,x,z,y)).