Algorithms and Complexity of Constraint Languages

Many computational problems in theoretical computer science can be parametrized in a natural way using so- called constraint languages. A well-known example here is the constraint satisfaction problem, but this also concerns optimization problems, quantified constraint satisfaction, problems about counting solutions, enumeration/listing problems, default logic, deciding entailment for logical theories, abduction, propositional circumscription, and more. A constraint language is the set of types of constraints that can be used in the specification of the input instances. The problems mentioned above are usually hard in general, but frequently turn out to be computationally feasible for many interesting constraint languages. The parametrization by constraint languages has been an extremely fruitful approach to study the computational complexity of problems in theoretical computer science: on the practical side, many restrictions of those problems that have been studied in the literature can be modeled by specifying an appropriate constraint language, and can hence be treated systematically and in a general framework. On the theoretical side, there is a wealth of mathematical tools that can be used both to derive algorithms and to derive hardness results, and the interactions with the related areas in mathematics (graph theory, combinatorics, universal algebra, finite model theory) keeps on fascinating and attracting researchers from various backgrounds. Besides the primary interest in the mentioned computational problems, so-called meta-problems about constraint languages have lately come into focus: these are computational problems where the constraint language itself is part of the input, and certain questions, usually about the expressive power of the constraint language, must be decided. These meta-problems arise naturally when we want to analyze the computational complexity of one of the tasks mentioned above for a given constraint language. Surprisingly, the meta-questions themselves frequently turn out to be decidable, or even tractable. In this project we study computational problems for constraint languages. Our attention is not restricted to the constraint satisfaction problem: we are interested in results that are useful more generally for all problems that are parametrized by constraint languages. Moreover, we systematically study the complexity of meta-problems; these problems are relevant for all the mentioned computational tasks.

Constraints are everywhere, in everyday life as well as in science and engineering. They may specify for instance that each class of students has to take certain subjects in particular rooms that no teacher can take care of more than one class at a time, and so on. The task of finding solutions that satisfy all constraints (class schedules for a school in our example) is called constraint satisfaction problem (CSP). The difficulty of finding solutions de- pends on the type of constraints that are needed to specify the situation. In the past decades literally hundreds of types have been analyzed, leading to efficient methods for solving many CSPs or to a deeper understanding of the inherent difficulties.One tool that is particularly useful for this analysis is so-called functional clones. A clone in the mathematical sense is a family of functions sharing certain properties. It turned out that clones are tightly related to certain constraints such that they can serve as unique fingerprints: Constraints with the same fingerprint can be solved by the same method, with the same effort. Therefore the analysis of new CSPs is guided by the knowledge about functional clones as provided by algebra.In this project we have investigated new types of constraints and developed the corresponding clone-based methods. Moreover, we answered questions regarding the structure of solutions: Given a solution, how can we find further, similar ones? How close can such solution be together? Given a wrong solution, how can we find the closest correct one?