Authors: Manuel Bodirsky ; Antoine Mottet

Many natural decision problems can be formulated as constraint satisfaction problems for reducts $\mathbb{A}$ of finitely bounded homogeneous structures. This class of problems is a large generalisation of the class of CSPs over finite domains. Our first result is a general polynomial-time reduction from such infinite-domain CSPs to finite-domain CSPs. We use this reduction to obtain new powerful polynomial-time tractability conditions that can be expressed in terms of the topological polymorphism clone of $\mathbb{A}$. Moreover, we study the subclass $\mathcal{C}$ of CSPs for structures $\mathbb{A}$ that are reducts of a structure with a unary language. Also this class $\mathcal{C}$ properly extends the class of all finite-domain CSPs. We apply our new tractability conditions to prove the general tractability conjecture of Bodirsky and Pinsker for reducts of finitely bounded homogeneous structures for the class $\mathcal{C}$.

• 03C15 - Model theory of denumerable and separable structures
• 08A40 - Operations and polynomials in algebraic structures, primal algebras
• 08A70 - Applications of universal algebra in computer science
• 68Q17 - Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
• 68Q25 - Analysis of algorithms and problem complexity