Options
A dichotomy for first-order reducts of unary structures
Publikationstyp
Journal Article
Date Issued
2018-05-22
Sprache
English
Author(s)
Volume
14
Issue
2
Article Number
13
Citation
Logical Methods in Computer Science 14 (2) : 13 (2018-05-22)
Publisher DOI
Scopus ID
Many 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.