Tue, 31 Jan 2023, 1:25 pm MST
For a given relational structure $\mathfrak B$, the constraint satisfaction problem CSP($\mathfrak B$) asks whether a given finite input structure maps homomorphically to $\mathfrak B$. We study the complexity of CSP($\mathfrak B$), where the domain of $\mathfrak B$ is infinite. Our basic setting is that if we have a complexity classification for the CSPs of first-order expansions of a structure $\mathfrak B$, then it can be transferred to obtain a classification of the CSPs of first-order expansions of another structure $\mathfrak C$. We exploit the algebraic product of structures that corresponds to the product of the respective polymorphism clones and present a complete complexity classification of the CSPs for first-order expansions of finite algebraic powers of $({\mathbb Q};<)$. By combining our classification result with classification transfer techniques, we answer several open questions in spatial reasoning from (Balbiani, Condotta, 2002), (Balbiani, Condotta, del Cerro, 1999) and (Balbiani, Condotta, del Cerro, 2002).
This is joint work with Manuel Bodirsky, Peter Jonsson, Barnaby Martin and Antoine Mottet.