Bodirsky, ManuelManuelBodirskyMottet, AntoineAntoineMottet2022-03-242022-03-242018-05-22Logical Methods in Computer Science 14 (2) : 13 (2018-05-22)http://hdl.handle.net/11420/12091Many natural decision problems can be formulated as constraint satisfaction problems for reducts 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 A. Moreover, we study the subclass C of CSPs for structures A that are reducts of a structure with a unary language. Also this class 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 C.en1860-597420182Journal Article10.23638/LMCS-14(2:13)2018Other