A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916240624189440 |
|---|---|
| author | Bodirsky, Manuel Bodor, Bertalan |
| author_facet | Bodirsky, Manuel Bodor, Bertalan |
| contents | Constraint satisfaction problems (CSPs) 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 defined 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 well-studied spatial reasoning formalism RCC5. We also classify which of these CSPs can be expressed in Datalog. Our method relies on Ramsey theory; we prove that RCC5 has a Ramsey order expansion. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2008_10261 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory Bodirsky, Manuel Bodor, Bertalan Logic 03C10, 03C05, 03C98, 03C40, 03C35 F.2.2; F.4.1 Constraint satisfaction problems (CSPs) 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 defined 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 well-studied spatial reasoning formalism RCC5. We also classify which of these CSPs can be expressed in Datalog. Our method relies on Ramsey theory; we prove that RCC5 has a Ramsey order expansion. |
| title | A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory |
| topic | Logic 03C10, 03C05, 03C98, 03C40, 03C35 F.2.2; F.4.1 |
| url | https://arxiv.org/abs/2008.10261 |