A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
Abstract
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 apply these conditions to obtain a new complexity dichotomy for CSPs of 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.
Details
| Originalsprache | Englisch |
|---|---|
| Aufsatznummer | 10 |
| Seitenumfang | 39 |
| Fachzeitschrift | ACM transactions on computation theory : TOCT |
| Jahrgang | 16 |
| Ausgabenummer | 2 |
| Publikationsstatus | Veröffentlicht - Juni 2024 |
| Peer-Review-Status | Ja |
Externe IDs
| Scopus | 85195842336 |
|---|---|
| dblp | journals/toct/BodirskyB24 |
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- computational complexity, Constraint satisfaction, model theory, ramsey theory, RCC5, spatial reasoning, universal algebra