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;<)$.

@article{paperbot1700,
  title = {Tractable Combinations of Temporal CSPs},
  author = {Manuel Bodirsky and Johannes Greiner and Jakub Rydval},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 18, Issue 2},
  year = {2022},
  doi = {10.46298/lmcs-18(2:11)2022}
}