The tractable-or-NP-hard dichotomy conjecture for generic combinations

Let $\mathfrak{A}_1$ and $\mathfrak{A}_2$ be countably infinite $\omega$-categorical structures without algebraicity, not preserved by all permutations, and with the cross prevention property. A binary injective polymorphism is a binary operation preserving all relations of a structure and injective as a function; a constant polymorphism is a constant operation preserving all relations. The constraint satisfaction problem of a structure $\mathfrak{A}$ is denoted by $\mathrm{CSP}(\mathfrak{A})$, and $\operatorname{Th}(\mathfrak{A})$ denotes its theory.

Tractable-or-NP-hard dichotomy conjecture. If either

• $\mathrm{CSP}(\mathfrak{A}_i)$ is in P and $\mathfrak{A}_i$ has a binary injective polymorphism for both $i=1$ and $i=2$, or
• $\mathfrak{A}_i$ has a constant polymorphism for both $i=1$ and $i=2$,

then

$$\mathrm{CSP}(\operatorname{Th}(\mathfrak{A}_1)\cup\operatorname{Th}(\mathfrak{A}_2))$$

is in P. Otherwise,

$$\mathrm{CSP}(\operatorname{Th}(\mathfrak{A}_1)\cup\operatorname{Th}(\mathfrak{A}_2))$$

is NP-hard.

The conjecture would extend the paper's tractability and hardness results to combinations of broad classes of countably infinite $\omega$-categorical structures with cross prevention. It remains open in general.