The CSP of a first-order theory T is the problem of deciding for a given finite set S of atomic formulas whether T ⋃ 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 CSP(T_{1} ⋃ T_{2}) under the assumption that CSP(T_{1}) and CSP(T_{2}) are decidable (or polynomial-time decidable). We show that for a large class of ω-categorical theories T_{1}, T_{2} the Nelson-Oppen conditions are not only sufficient, but also necessary for polynomial-time tractability of CSP(T_{1} ⋃ T_{2}) (unless P=NP).

Complexity of Combinations of Qualitative Constraint Satisfaction Problems