Project number		International Programs  I836
Title		Lead Agency Verfahren_ANR Frankreich 2011 2011_Algorithms and Complexity of Constraint Languages
Principal investigator		SALZER Gernot
Approval date		17.12.2011
University / Research institution		Institut für Computersprachen Abteilung für Theoretische Informatik und Logik, Technische Universität Wien
Scientific field(s)
Keywords		constraint satisfacion problems, Partial clones, computational complexity, many-valued logics, constraint languages
Homepage		http://www.logic.at/staff/salzer/

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.