Allgorithmen für und Komplexität von Constraint-Sprachen

Viele Berechnungsprobleme der theoretischen Informatik können auf natürliche Art durch sogenannte Constraint- Sprachen parametrisiert werden. Ein bekanntes Beispiel dafür ist das Erfüllbarkeitsproblem von Constraints (Constraint Satisfaction Problem), dasselbe gilt aber auch für Optimierungsprobleme, für die Erfüllbarkeit quantifizierter Constraints, für Abzähl- und Aufzählungsprobleme, für die Entscheidbarkeit der Konsequenzrelation logischer Theorien, Abduktion, propositionale Circumscription, und mehr. Eine Constraint-Sprache ist die Menge der Constraint-Typen, die in der Spezifikation von Probleminstanzen verwendet werden können. Die oben angeführten Probleme sind im Allgemeinen hart, stellen sich aber bei Einschränkung auf viele interessante Constraint-Sprachen als effizient lösbar heraus. Die Parametrisierung durch Constraint-Sprachen hat sich als ein sehr fruchtbarer Ansatz erwiesen, um die Berechnungskomplexität von Problemen der theoretischen Informatik zu untersuchen. Einerseits können viele Teilprobleme, die im Lauf der Jahre in der Literatur beschrieben wurden, durch die Wahl geeigneter Constraint-Sprachen modelliert und dadurch systematisch in einem einheitlichen Rahmen behandelt werden. Andererseits gibt es eine reichhaltige Auswahl an mathematischen Werkzeugen aus Gebieten wie der Graphentheorie, der Kombinatorik, der universellen Algebra und der Theorie endlicher Modelle, die sich sowohl zur Konstruktion von Algorithmen als auch zum Beweis von Komplexitätsresultaten eignen. Neben den oben erwähnten Fragestellungen fanden in letzter Zeit sogenannte Meta-Probleme von Constraint- Sprachen zunehmend Beachtung: das sind Berechnungsprobleme, bei denen die Constraint-Sprache selber Teil der Eingabe ist und bestimmte Fragen, typischer Weise hinsichtlich der Ausdrucksstärke der Constraint-Sprachen, entschieden werden müssen. Diese Meta-Probleme treten in natürlicher Weise auf, wenn man die Berechnungskomplexität einer der oben erwähnten Aufgaben für eine gegebene Constraint-Sprache analysiert. Überraschenderweise stellen sich die Meta-Probleme häufig als entscheidbar oder sogar als effizient lösbar heraus. In diesem Projekt untersuchen wir verschiedene Berechnungsprobleme von Constraint-Sprachen. Wir sind nicht nur am Erfüllbarkeitsproblem interessiert, sondern streben Resultate an, die auf alle durch Constraint-Sprachen parametriesierte Probleme anwendbar sind. Weiters analysieren wir systematisch die Komplexität von Meta- Problemen.

Einschränkungen und Bedingungen (Constraints) begegnen wir auf Schritt und Tritt, im Alltag ebenso wie in Wissenschaft und Technik. Beispiels- weise muss jede Schulklasse gemäß Lehrplan in bestimmten Gegenständen unterrichtet werden, die wiederum in speziellen Räumen stattfinden müssen, wobei jeder Lehrer zeitgleich höchstens eine Klasse unterrichten kann, und so weiter. Die Aufgabe Lösungen zu finden, die alle Anforderungen erfüllen, in unserem Beispiel Stundenpläne für eine ganze Schule wird Erfüllungsproblem (Constraint Satisfaction Problem) genannt. Die Schwierigkeit dieser Aufgabe hängt von der Art der Bedingungen ab, die in der Problemstellung auftreten. In den vergangenen Jahrzehnten wurden zahlreiche Arten untersucht, wodurch wir nun für viele Erfüllungsprobleme effiziente Losungsmethoden kennen bzw. verstehen, warum manche davon schwierig sind.Ein Werkzeug, das sich bei diesen Untersuchungen als besonders nützlich erweist, sind funktionale Klone. Ein Klon im mathematischen Sinn, ist eine Familie von Funktionen mit gewissen gemeinsamen Eigenschaften. Wie sich herausstellt, besteht eine enge Beziehung zwischen Klonen und Erfüllungsproblemen, sodass Klone als eindeutige Fingerabdrücke dienen können: Probleme mit demselben Fingerabdruck können mit denselben Methoden und demselben Aufwand gelöst werden. Aus diesem Grund lässt man sich bei der Analyse neuer Erfüllungsprobleme vom Wissen über Klone leiten, wie es die Algebra zur Verfügung stellt.In diesem Projekt wurden nicht nur neue Arten von Constraints untersucht und die zugehörigen Klon-Methoden entwickelt, sondern es wurden auch Fragen zur Struktur der Lösungen beantwortet, wie etwa: Gegeben eine Losung, wie findet man eine weitere, möglichst ähnliche? Wie nahe liegen Lösungen beisammen? Gegeben eine falsche Lösung, wie lässt sich die nächstliegende korrekte Lösung finden?