Canonical Polymorphisms of Ramsey Structures and the Unique Interpolation Property.
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
Constraint satisfaction problems for first-order reducts of finitely bounded homogeneous structures form a large class of computational problems that might exhibit a complexity dichotomy, P versus NP-complete. A powerful method to obtain polynomial-time tractability results for such CSPs is a certain reduction to polynomial-time tractable finite-domain CSPs de-fined over k-types, for a sufficiently large k. We give sufficient conditions when this method can be applied and illustrate how to use the general results to prove a new complexity dichotomy for first-order expansions of the basic relations of the spatial reasoning formalism RCC5.
Details
Originalsprache | Englisch |
---|---|
Titel | 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021 |
Seiten | 1-13 |
Seitenumfang | 13 |
Publikationsstatus | Veröffentlicht - 29 Juni 2021 |
Peer-Review-Status | Ja |
Externe IDs
Scopus | 85110859569 |
---|---|
ORCID | /0000-0001-8228-3611/work/142241143 |