Options
Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
Publikationstyp
Conference Paper
Date Issued
2016-07
Sprache
English
Author(s)
Start Page
623
End Page
632
Citation
31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016)
Contribution to Conference
Publisher DOI
Scopus ID
Many 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.
Subjects
abstract tractability conditions
canonical functions
constraint satisfaction problems