Manuel Bodirsky

Set Constraints: Algorithms and Complexity

Project description

Constraint satisfaction problems for set constraints have particularly many links to other areas in computer science, in particular to artificial intelligence, description logics, but also to type inference for programming languages. In this project, we want to systematically study the computational complexity of CSPs for set constraint languages. Formally, a set constraint language is a relational structure with a first-order definition in the countable atomless boolean algebra. This class of constraint languages contains many surprizingly rich and expressive formalisms whose CSP can still be solved in polynomial time. In our systematic approach, we expect to find interesting new tractable set constraint languages, and also expect to find tractable generalizations of known formalisms. We aim to find a list of all tractable set constraint languages, and we want to prove that every set constraint language that is not contained in one of the languages from our list is NP-complete. For achieve this goal, we can apply the universal-algebraic approach to constraint satisfaction.

Goals

Implement and generalize the existing algorithms for set constraints. The topic described above is well-suited for a subsequent dissertation.

Prerequisites

Candidates for this project should have a good background in logic, algorithms, and complexity.

Print version

A project description in pdf.