A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory
Preprint
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 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.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- CLASSIFICATION OF $\omega $ -CATEGORICAL MONADICALLY STABLE STRUCTURESThe Journal of Symbolic Logic, 2023
- CORES OVER RAMSEY STRUCTURESThe Journal of Symbolic Logic, 2021
- Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)SIAM Journal on Computing, 2020
- PROJECTIVE CLONE HOMOMORPHISMSThe Journal of Symbolic Logic, 2019
- The wonderland of reflectionsIsrael Journal of Mathematics, 2017
- Qualitative Temporal and Spatial Reasoning RevisitedJournal of Logic and Computation, 2009
- Affine systems of equations and counting infinitary logicTheoretical Computer Science, 2009
- Existence theorems for weakly symmetric operationsAlgebra universalis, 2008
- The Complexity of Equality Constraint LanguagesLecture Notes in Computer Science, 2006
- The Core of a Countably Categorical StructureLecture Notes in Computer Science, 2005