Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
Abstract
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.
Details
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016 |
| Publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| Pages | 623-632 |
| Number of pages | 10 |
| ISBN (electronic) | 9781450343916 |
| Publication status | Published - 5 Jul 2016 |
| Peer-reviewed | Yes |
Conference
| Title | 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016 |
|---|---|
| Duration | 5 - 8 July 2016 |
| City | New York |
| Country | United States of America |
External IDs
| ORCID | /0000-0001-8228-3611/work/142241101 |
|---|
Keywords
ASJC Scopus subject areas
Keywords
- abstract tractability conditions, canonical functions, constraint satisfaction problems