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.