The Complexity of Combinations of Qualitative Constraint Satisfaction Problems by Manuel Bodirsky, Johannes Greiner

“…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).…”
Get full text