Locally finite Constraint Satisfaction Problems

Many natural computational problems, such as satisfiability and systems of equations, can be expressed in a unified way as constraint satisfaction problems (CSPs).  They can be understood as asking whether there is a homomorphism between two relational structures over the same signature.  We consider structures whose elements are built of so-called atoms, and defined using finitely many FO formulas.  Both the domain and the number of relations of such structures are usually infinite, but thanks to the finite presentation they can be treated as an input for algorithms.

A relational structure T is locally finite if every relation of T is finite.  We use recent results in topological dynamics to prove that it is decidable whether there exists a homomorphism from a relational structure A to a locally finite relational structure T.  As a corollary, we effectively characterise certain subclasses of CSPs solvable in polynomial time, with applications to descriptive complexity.

This is joint work with Bartek Klin, Eryk Kopczynski and Szymon Torunczyk.

Speaker biography

Joanna Ochremiak is a PhD student at the Institute of Informatics in the University of Warsaw.  Her research interests include finite model theory, automata theory, logic and constraint satisfaction.