Constraint satisfaction problems solvable by local consistency methods

Abstract

Das Bedingungserfüllungsproblem, kurz CSP, einer vorgegebenen relationalen Sprache, eine Menge mit hier endlich vielen Relationen, ist ein Entscheidungsproblem. Es fragt, ob Variablen eine Wertebelegung zulassen, sodass gewisse, aus der Sprache gebildete Bedingungen erfüllt sind. Die Schwierigkeit eines solchen Entscheidungsproblems wird festgelegt durch die Polymorphismen der entsprechenden relationalen Sprache, das sind Homomorphismen von endlichen Potenzen der Sprache auf sich selbst. Diese Arbeit soll eine mehrheitlich eigenständig lesbare Charakterisierung endlicher relationaler Sprachen bieten, deren CSP sich bereits durch das Überprüfen auf lokale Konsistenz lösen lässt. Die Terminologie inhaltlich relevanter Veröffentlichungen wird in dieser Arbeit vereinheitlicht und Beweise werden möglichst ausführlich erklärt. Wir definieren die Begriffe der Breite und der relationalen Breite einer endlichen Sprache. Falls eine Sprache beschränkte relationale Breite hat, geben beide Ausdrücke grob gesprochen die Anzahl an Variablen an, für die konsistente Belegungen existieren müssen, damit eine Instanz des CSP lösbar ist. Wir beweisen, dass jede endliche relationale Sprache genau dann beschränkte relationale Breite hat, wenn sie in gewissem Sinne nicht das Lösen von linearen Gleichungen über einem endlichen Primkörper simulieren kann. In diesem Fall kann das entsprechende CSP einer endlichen Sprache bereits durch Betrachtung der zulässigen Belegungen von nur jeweils drei Variablen gleichzeitig gelöst werden. Endliche Sprachen mit beschränkter relationaler Breite können auch durch die Existenz von Polymorphismen charakterisiert werden, welche gewisse, nicht-triviale Gleichungen erfüllen. Dies ermöglicht in weiterer Folge Aussagen über die Entscheidbarkeit der Klasse aller endlicher relationaler Sprachen mit beschränkter relationaler Breite.

The constraint satisfaction problem, short CSP, of a given constraint language, a set together with finitely many relations, is a decision problem. It asks whether variables can be assigned values such that constraints built from the constraint language are satisfied. The hardness of this decision problem is determined by the homomorphisms from finite powers of the constraint language to itself, called polymorphisms. This thesis aims to unify terminology of relevant papers and explain proofs in detail to provide a mostly self-contained characterization of finite constraint languages that give rise to CSPs solvable by local consistency methods. To that end, we define the notions of width and of relational width of a finite constraint language. For languages of bounded relational width, both notions indicate the number of variables upon which consistency must be enforced at a time to solve the corresponding CSP. We prove that a finite constraint language has bounded relational width iff it cannot, in some sense, simulate the problem of solving linear equations over a finite prime field. In that case, the CSP over a finite constraint language is already solvable by local propagation by considering only three variables at a time. Lastly, we show that finite constraint languages of bounded relational width are characterized by the existence of polymorphisms that satisfy certain non-trivial identities. This provides insight to the meta-question of deciding bounded relational width for finite constraint languages.