Tractable Combinations of Temporal CSPs

MaRDI QIDQ6355741arXivFDO

Authors Manuel Bodirsky, Johannes Greiner, Jakub Rydval

Publication date 10 December 2020

Published in arXiv

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

arXiv classification

cs.CCcs.LOmath.LO

Abstract: The constraint satisfaction problem (CSP) of a first-order theory T is the computational problem of deciding whether a given conjunction of atomic formulas is satisfiable in some model of T. We study the computational complexity of CSP$(T_{1}cup{T}_2)$ where $T_1$ and $T_2$ are theories with disjoint finite relational signatures. We prove that if $T_1$ and $T_2$ are the theories of temporal structures, i.e., structures where all relations have a first-order definition in $(Q;<)$, then CSP$(T_{1}cup{T}_2)$ is in P or NP-complete. To this end we prove a purely algebraic statement about the structure of the lattice of locally closed clones over the domain $Q$ that contain Aut$(Q;<)$.

This page was built for publication: Tractable Combinations of Temporal CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6355741)