Bodirsky, ManuelManuelBodirskyMottet, AntoineAntoineMottet2022-03-242022-03-242016-0731st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016)http://hdl.handle.net/11420/12095Many natural decision problems can be formulated as constraint satisfaction problems for reducts 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 topological polymorphism clones. Moreover, we study the subclass C of CSPs for structures that are first-order definable over equality with parameters. Also this class C properly extends the class of all finite-domain CSPs. We show that the tractability conjecture for reducts of finitely bounded homogeneous structures is for C equivalent to the finite-domain tractability conjecture.enabstract tractability conditionscanonical functionsconstraint satisfaction problemsConference Paper10.1145/2933575.2934515Other