A Dichotomy for First-Order Reducts of Unary Structures

Many natural decision problems can be formulated as constraint satisfactionproblems for reducts $\mathbb{A}$ of finitely bounded homogeneous structures.This class of problems is a large generalisation of the class of CSPs overfinite domains. Our first result is a general polynomial-time reduction fromsuch infinite-domain CSPs to finite-domain CSPs. We use this reduction toobtain new powerful polynomial-time tractability conditions that can beexpressed 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 thisclass $\mathcal{C}$ properly extends the class of all finite-domain CSPs. Weapply our new tractability conditions to prove the general tractabilityconjecture of Bodirsky and Pinsker for reducts of finitely bounded homogeneousstructures for the class $\mathcal{C}$