Algorithms and Complexity of Constraint Languages

This project is funded by

FWF logo

and

Logo Agence Nationale de la Recherche

German title

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

Project identifier

I 836 (International projects)

Project leaders

Gernot Salzer / Miki Hermann

Principal investigators (Austrian side)

Duration

1 Jul 2012 – 30 Jun 2015

Disciplines

Computer Science (50 %) / Mathematics (50 %)

Key words

constraint satisfaction problem, clone, partial clone, computational complexity, many-valued logics, constraint languages

Abstract

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.

German version (opens in a new tab)