ALgorithms and COmplexity for Constraint LANguages – ALCOCLAN

Many computational problems in theoretical computer science can be
parametrized in a natural way using so-called constraint languages. A
famous 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.