  The CSP of a first-order theory $T$ is the problem of deciding for a given
finite set $S$ of atomic formulas whether $T \cup S$ is satisfiable. Let $T_1$
and $T_2$ be two theories with countably infinite models and disjoint
signatures. Nelson and Oppen presented conditions that imply decidability (or
polynomial-time decidability) of $\mathrm{CSP}(T_1 \cup T_2)$ under the
assumption that $\mathrm{CSP}(T_1)$ and $\mathrm{CSP}(T_2)$ are decidable (or
polynomial-time decidable). We show that for a large class of
$\omega$-categorical theories $T_1, T_2$ the Nelson-Oppen conditions are not
only sufficient, but also necessary for polynomial-time tractability of
$\mathrm{CSP}(T_1 \cup T_2)$ (unless P=NP).
