Abstract

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 is 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 characterize certain subclasses of CSPs solvable in polynomial time, with applications to descriptive complexity .

Joint work with Bartek Klin, Eryk Kopczyński and Szymon Toruńczyk.