# The Complexity of Combinations of Qualitative Constraint Satisfaction
Problems 111Both authors have received funding from the European Research
Council (ERC Grant Agreement no. 681988), the German Research Foundation (DFG,
project number 622397), and the DFG Graduiertenkolleg 1763 (QuantLA).
In contrast to the conference version [BodirskyGreiner18], this is the full
article with all proofs and a stronger main result (Theorem 1.4).

Manuel Bodirsky  and  Johannes Greiner  Institut für Algebra, TU Dresden

###### Abstract.

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
$\operatorname{CSP}(T_{1}\cup T_{2})$ under the assumption that
$\operatorname{CSP}(T_{1})$ and $\operatorname{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
$\operatorname{CSP}(T_{1}\cup T_{2})$ (unless P=NP).

##  1\. Introduction

Two independent proofs of the finite-domain constraint satisfaction
tractability conjecture have recently been published by Bulatov and Zhuk [20,
29], settling the Feder-Vardi dichotomy conjecture. In contrast, the
computational complexity of constraint satisfaction problems over infinite
domains cannot be classified in general [8]. However, for a restricted class
of constraint satisfaction problems that strictly contains all finite-domain
CSPs and captures the vast majority of the problems studied in _qualitative
reasoning_ (see the survey article [9]) there also is a tractability
conjecture (see [16, 4, 5, 3]). The situation is similar to the situation for
finite-domain CSPs before Bulatov and Zhuk: there is a formal condition which
provably implies NP-hardness, and the conjecture is that every other CSP in
the class is in P.

For finite domain CSPs, it turned out that only few fundamentally different
algorithms were needed to complete the classification; the key in both the
solution of Bulatov and the solution of Zhuk was a clever combination of the
existing algorithmic ideas. An intensively studied method for obtaining
(polynomial-time) decision procedures for infinite-domain CSPs is the Nelson-
Oppen combination method; see, e.g., [2, 28]. The method did not play any role
for the classification of finite-domain CSPs, but is extremely powerful for
combining algorithms for infinite-domain CSPs.

In order to conveniently state what type of combinations of CSPs can be
studied with the Nelson-Oppen method, we slightly generalise the notion of a
CSP. The classical definition is to fix an infinite structure $\mathfrak{B}$
with finite relational signature $\tau$; then
$\operatorname{CSP}(\mathfrak{B})$ is the computational problem of deciding
whether a given finite set of _atomic $\tau$-formulas_ (i.e., formulas of the
form $x_{1}=x_{2}$ or of the form $R(x_{1},\dots,x_{n})$ for $R\in\tau$ and
variables $x_{1},\dots,x_{n}$) is satisfiable in $\mathfrak{B}$. Instead of
fixing a $\tau$-structure $\mathfrak{B}$, we fix a _$\tau$ -theory $T$_ (i.e.,
a set of first-order $\tau$-sentences). Then $\operatorname{CSP}(T)$ is the
computational problem of deciding for a given finite set $S$ of atomic
$\tau$-formulas whether $T\cup S$ has a model. Clearly, this is a
generalisation of the classical definition since
$\operatorname{CSP}(\mathfrak{B})$ is the same as
$\operatorname{CSP}(\operatorname{Th}(\mathfrak{B}))$ where
$\operatorname{Th}(\mathfrak{B})$ is the _first-order theory of
$\mathfrak{B}$_, i.e., the set of all first-order sentences that hold in
$\mathfrak{B}$. The definition for theories is _strictly_ more expressive (we
give an example in Section 2 that shows this).

Let $T_{1}$ and $T_{2}$ be two theories with disjoint finite relational
signatures $\tau_{1}$ and $\tau_{2}$. We are interested in the question when
$\operatorname{CSP}(T_{1}\cup T_{2})$ can be solved in polynomial time; we
refer to this problem as the _combined CSP_ for $T_{1}$ and $T_{2}$. Clearly,
if $\operatorname{CSP}(T_{1})$ or $\operatorname{CSP}(T_{2})$ is NP-hard, then
$\operatorname{CSP}(T_{1}\cup T_{2})$ is NP-hard, too. Suppose now that
$\operatorname{CSP}(T_{1})$ and $\operatorname{CSP}(T_{2})$ can be solved in
polynomial-time. In this case, there are examples where
$\operatorname{CSP}(T_{1}\cup T_{2})$ is in P, and examples where
$\operatorname{CSP}(T_{1}\cup T_{2})$ is NP-hard. Even if we know the
complexity of $\operatorname{CSP}(T_{1})$ and of $\operatorname{CSP}(T_{2})$,
a classification of the complexity of $\operatorname{CSP}(T_{1}\cup T_{2})$
for arbitrary theories $T_{1}$ and $T_{2}$ is too ambitious (see Section 5 for
a formal justification). But such a classification should be feasible at least
for the mentioned class of infinite-domain CSPs for which the tractability
conjecture applies.

###  1.1. Qualitative CSPs

The idea of _qualitative formalisms_ is that reasoning tasks (e.g. about space
and time) is not performed with absolute numerical values, but rather with
_qualitative_ predicates (such as _within_ , _before_ , etc.). There is no
universally accepted definition in the literature that defines what a
_qualitative CSP_ is, but a proposal has been made in [9]; the central
mathematical property for this proposal is _$\omega$ -categoricity_. A theory
is called _$\omega$ -categorical_ if it has up to isomorphism only one
countable model. A structure is called _$\omega$ -categorical_ if and only if
its first-order theory is $\omega$-categorical. Examples are
$({\mathbb{Q}};<)$, Allen’s Interval Algebra, and more generally all
homogeneous structures with a finite relational signature (a structure
$\mathfrak{B}$ is called _homogeneous_ if all isomorphisms between finite
substructures can be extended to an automorphism; see [24, 6]). The class of
CSPs for $\omega$-categorical theories arguably coincides with the class of
CSPs for _qualitative formalisms_ studied e.g. in temporal and spatial
reasoning; see [9].

For an $\omega$-categorical theory $T$, the complexity of
$\operatorname{CSP}(T)$ can be studied using the universal-algebraic approach
that led to the proof of the Feder-Vardi dichotomy conjecture. A _signature_
is a set of function and relation symbols together with an arity for each
symbol. Let $\tau$ be a signature. A _$\tau$ -structure_ $\mathfrak{B}$ is a
set $B$ together with an $n$-ary function on $B$ for each $n$-ary function
symbol in $\tau$ and an $n$-ary relation over $B$ for each $n$-ary relation
symbol in $\tau$. All signatures of structures in this article are assumed to
be countable. One of the central concepts for the universal-algebraic approach
is the concept of a _polymorphism_ of a structure $\mathfrak{B}$, i.e., a
homomorphism from $\mathfrak{B}^{k}$ to $\mathfrak{B}$ for some
$k\in{\mathbb{N}}$. It is known that the polymorphisms of a finite structure
$\mathfrak{B}$ fully capture the complexity of
$\operatorname{CSP}(\mathfrak{B})$ up to P-time reductions (in fact, up to
Log-space reductions; see [23] for a collection of survey articles about the
complexity of CSPs), and the same is true for structures $\mathfrak{B}$ with
an $\omega$-categorical theory [15]. In order to understand when we can apply
the universal-algebraic approach to study the complexity of
$\operatorname{CSP}(T_{1}\cup T_{2})$, we need to understand the following
fundamental question.

Question 1: Suppose that $T_{1}$ and $T_{2}$ are theories with disjoint finite
relational signatures $\tau_{1}$ and $\tau_{2}$. When is there an
$\omega$-categorical $(\tau_{1}\cup\tau_{2})$-theory $T$ such that
$\operatorname{CSP}(T)$ equals $\operatorname{CSP}(T_{1}\cup T_{2})$, i.e.,
for all sets $S$ of atomic $(\tau_{1}\cup\tau_{2})$-formulas, we have that
$S\cup T$ is satisfiable if and only if $S\cup(T_{1}\cup T_{2})$ is
satisfiable?

Note that $\omega$-categorical theories are _complete_ , i.e., for every
first-order sentence $\phi$ either $T$ implies $\phi$ or $T$ implies
$\neg\phi$. In general, it is not true that $\operatorname{CSP}(T_{1}\cup
T_{2})$ equals $\operatorname{CSP}(T)$ for a complete theory $T$ (we present
an example in Section 2).

Question 1 appears to be very difficult in general, in particular when
considering the work of Braunfeld [18] in the context of Proposition 2.1.
However, we present a broadly applicable condition for $\omega$-categorical
theories $T_{1}$ and $T_{2}$ with infinite models that implies the existence
of an $\omega$-categorical theory $T$ such that $\operatorname{CSP}(T_{1}\cup
T_{2})$ equals $\operatorname{CSP}(T)$ (Proposition 1.1 below). The theory $T$
that we construct has many useful properties. In particular $T_{1}\cup
T_{2}\subseteq T$ and

  1. (1)

if $\phi_{1}(\bar{x})$ is a $\tau_{1}$-formula and $\phi_{2}(\bar{x})$ is a
$\tau_{2}$-formula, both with free variables $\bar{x}=(x_{1},\dots,x_{n})$,
then
$T\models\exists\bar{x}(\phi_{1}(\bar{x})\wedge\phi_{2}(\bar{x})\wedge\bigwedge_{i<j}x_{i}\neq
x_{j})$ if and only if
$T_{1}\models\exists\bar{x}(\phi_{1}(\bar{x})\wedge\bigwedge_{i<j}x_{i}\neq
x_{j})$ and
$T_{2}\models\exists\bar{x}(\phi_{2}(\bar{x})\wedge\bigwedge_{i<j}x_{i}\neq
x_{j})$;

  2. (2)

For every $(\tau_{1}\cup\tau_{2})$-formula $\phi$ there exists a conjunction
of $\tau_{1}$ and $\tau_{2}$ formulas that is equivalent to $\phi$ modulo $T$.

In fact, $T$ is uniquely given by these three properties (up to equivalence of
theories; see Lemma 2.8) and again $\omega$-categorical, and we call it the
_generic combination of $T_{1}$ and $T_{2}$_. Let $\mathfrak{B}_{1}$ and
$\mathfrak{B}_{2}$ be two $\omega$-categorical relational structures whose
first-order theories have a generic combination $T$; then we call the (up to
isomorphism unique) countably infinite model of $T$ the _generic combination
of $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$_.

###  1.2. The Nelson-Oppen Criterion

Let $T_{1},T_{2}$ be theories with disjoint finite signatures
$\tau_{1},\tau_{2}$ and suppose that $\operatorname{CSP}(T_{1})$ is in P and
$\operatorname{CSP}(T_{2})$ is in P. Nelson and Oppen gave sufficient
conditions for $\operatorname{CSP}(T_{1}\cup T_{2})$ to be solvable in
polynomial time, too. Their conditions are:

  1. (1)

Both $T_{1}$ and $T_{2}$ are _stably infinite_ : a $\tau$-theory $T$ is called
_stably infinite_ if for every quantifier-free $\tau$-formula
$\phi(x_{1},\dots,x_{n})$, if $\phi$ is satisfiable over $T$, then there also
exists an _infinite_ model $\mathfrak{A}$ and elements $a_{1},\dots,a_{n}$
such that $\mathfrak{A}\models\phi(a_{1},\dots,a_{n})$.

  2. (2)

for $i=1$ and $i=2$, the signature $\tau_{i}$ contains a binary relation
symbol $\neq_{i}$ that denotes the disequality relation, i.e., $T_{i}$ implies
the sentence $\forall x,y\,(x\neq_{i}y\Leftrightarrow\neg(x=y))$;

  3. (3)

Both $T_{1}$ and $T_{2}$ are _convex_ (here we follow established
terminology). A $\tau$-theory $T$ is called _convex_ if for every finite set
$S$ of atomic $\tau$-formulas the set $T\cup S\cup\\{x_{1}\neq
y_{1},\dots,x_{m}\neq y_{m}\\}$ is satisfiable whenever $T\cup
S\cup\\{x_{j}\neq y_{j}\\}$ is satisfiable for each $j\leq m$.

The assumption that a relation symbol denoting the disequality relation is
part of the signatures $\tau_{1}$ and $\tau_{2}$ is often implicit in the
literature treating the Nelson-Oppen method. It would be interesting to
explore when it can be dropped, but we will not pursue this question here. The
central question of this article is the following.

Question 2. In which settings are the Nelson-Oppen conditions (and in
particular, the convexity condition) not only sufficient, but also necessary
for polynomial-time tractability of the combined CSP?

Again, for general theories $T_{1}$ and $T_{2}$, this is a too ambitious
research goal; but we will study it for generic combinations of
$\omega$-categorical theories $T_{1},T_{2}$ with infinite models. In this
setting, the first condition that both $T_{1}$ and $T_{2}$ are stably infinite
is trivially satisfied. The third condition on $T_{i}$, convexity, is
equivalent to the existence of a binary injective polymorphism of the (up to
isomorphism unique) countably infinite model of $T_{i}$ (see Theorem 3.1). We
mention that binary injective polymorphisms played an important role in
several recent infinite-domain complexity classifications [12, 11, 25].

###  1.3. Results

To state our results concerning Question 1 and Question 2 we need basic
terminology for permutation groups. A permutation group $G$ on a set $A$ is
called

  * •

_$n$ -transitive_ if for all tuples $\bar{b},\bar{c}\in A^{n}$, each with
pairwise distinct entries, there exists a permutation $g\in G$ such that
$g(\bar{b})=\bar{c}$ (unary functions applied to tuples or multiple arguments
act componentwise and result in tuples). $G$ is called _transitive_ if it is
1-transitive.

  * •

_$n$ -set-transitive_ if for all subsets $B,C$ of $A$ with $|B|=|C|=n$ there
exists a permutation $g\in G$ such that $g(B)\mathrel{\vcentcolon=}\\{g(b)\mid
b\in B\\}=C$.

A structure is called _$n$ -transitive_ (or _$n$ -set-transitive_) if its
automorphism group is. The existence of generic combinations can be
characterised as follows (see Section 2 for the proof).

######  Proposition 1.1.

Let $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ be countably infinite
$\omega$-categorical structures with disjoint relational signatures. Then
$\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ have a generic combination if and
only if either both $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ do not have
algebraicity (in the model-theoretic sense; see Section 2) or one of
$\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ does have algebraicity and the other
has an automorphism group which is $n$-transitive for all $n\in{\mathbb{N}}$.

Our main result concerns Question 2 for generic combinations $\mathfrak{B}$ of
countably infinite $\omega$-categorical structures $\mathfrak{B}_{1}$ and
$\mathfrak{B}_{2}$; as we mentioned before, if the generic combination exists,
it is up to isomorphism unique, and again $\omega$-categorical.

Our result does not apply if one of the structures is too inexpressive. To
state the expressivity requirement we introduce further terminology. A
_primitive positive_ formula (_pp-formula_) is a conjunction of atomic
formulas where some variables can be existentially quantified. Likewise, a
relation $R\subseteq B^{n}$ is _pp-definable_ in a structure $\mathfrak{B}$ if
there exists a pp-formula $\phi$ such that $R=\left\\{\bar{x}\in
B^{n}\mid\mathfrak{B}\models\phi(\bar{x})\right\\}$. We call a tuple
_injective_ if all its coordinates are pairwise distinct.

For a fixed $\tau$-structure $\mathfrak{B}$ and a $\tau$-formula
$\phi(x_{1},\dotsc,x_{n})$ a map
$s\colon\left\\{x_{1},\dotsc,x_{n}\right\\}\rightarrow\mathfrak{B}$ such that
$\phi(s(x_{1}),\dotsc,s(x_{n}))$ is true in $\mathfrak{B}$ is a _solution_ to
$\phi$. The expressivity requirement for our result is captured in the
following notion.

######  Definition 1.2.

A structure $\mathfrak{B}$ _can prevent crosses_ if there exists a pp-formula
$\phi$ such that

  1. (1)

$\phi(x,y,u,v)\operatorname{\wedge}x=y$ has a solution $s$ over $\mathfrak{B}$
such that $s(x,u,v)$ is injective,

  2. (2)

$\phi(x,y,u,v)\operatorname{\wedge}u=v$ has a solution $s$ over $\mathfrak{B}$
such that $s(x,y,u)$ is injective,

  3. (3)

$\phi(x,y,u,v)\operatorname{\wedge}x=y\operatorname{\wedge}u=v$ has no
solution over $\mathfrak{B}$.

Any such formula $\phi$ will be referred to as a _cross prevention formula_ of
$\mathfrak{B}$.

To explain the naming, consider solutions $s_{1},\,s_{2}$ to a cross
prevention formula $\phi$ of a structure $\mathfrak{B}$ with images
$(x_{1},x_{1},u_{1},v_{1})$ and $(x_{2},y_{2},u_{2},u_{2})$ respectively, such
that $(x_{1},u_{1},v_{1})$ and $(x_{2},y_{2},u_{2})$ are injective. Let
$f\colon\mathfrak{B}^{k}\rightarrow\mathfrak{B}$ be a polymorphism of
$\mathfrak{B}$. If $R$ is a relation in $\mathfrak{B}$ and
$t_{1},\dotsc,t_{k}\in R$, then $f(t_{1},\dotsc,t_{k})\in R$ because $f$ is a
homomorphism ($f$ _preserves_ $R$). Preservation of relations transfers to any
relation which is pp-definable over $\mathfrak{B}$. Therefore, there is no
binary polymorphism $f$ of $\mathfrak{B}$ such that

$\displaystyle f(x_{1},x_{2})$ $\displaystyle=f(x_{1},y_{2})\quad\text{and}$
$\displaystyle f(u_{1},u_{2})$ $\displaystyle=f(v_{1},u_{2}),$

because the arguments of $f$ are in the relation defined by $\phi$, but the
image is not. This means that in Figure 1 either the vertical or the
horizontal identity (indicated by dashed lines) cannot hold, i.e., we will not
see a cross.

$u_{1}$$x_{1},y_{1}$$v_{1}$$x_{2}$$u_{2},v_{2}$$y_{2}$ Figure 1. An
illustration of the property to _prevent crosses_ from Definition 1.2. Dashed
edges indicate (potential) equalities between function values.

To simplify the presentation of our result and its proof, we introduce the
following shortcut.

######  Definition 1.3.

A countably infinite $\omega$-categorical structure has Property  _$J$_ if it

  * •

has a relational signature containing a binary symbol for the disequality
relation,

  * •

is 2-set-transitive,

  * •

can prevent crosses and

  * •

does not have algebraicity.

An easy example for such a structure is $(\mathbb{Q};<,\neq)$. Further
examples of structures with Property $J$ come from expansions of the countable
random tournament (see, e.g., Lachlan [26], see Section 2 for the definition
of expansion) and the countable homogeneous local order $S(2)$ (also see
[22]). More examples for structures with Property $J$ will be presented in
Section 4.

We now state our main result for Question 2. The proof can be found in Section
3.

######  Theorem 1.4.

Let $\mathfrak{B}$ be the generic combination of two countably infinite
$\omega$-categorical structures $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ with
Property $J$ and finite relational signature such that
$\operatorname{CSP}(\mathfrak{B}_{1})$ and
$\operatorname{CSP}(\mathfrak{B}_{2})$ are in P. Then one of the following
applies:

  * •

$\operatorname{Th}(\mathfrak{B}_{1})$ or $\operatorname{Th}(\mathfrak{B}_{2})$
is not convex; in this case, $\operatorname{CSP}(\mathfrak{B})$ is NP-hard.

  * •

Each of $\operatorname{Th}(\mathfrak{B}_{1})$ and
$\operatorname{Th}(\mathfrak{B}_{2})$ is convex, and
$\operatorname{CSP}(\mathfrak{B})$ is in P.

In other words, either the Nelson-Oppen conditions apply, and
$\operatorname{CSP}(\mathfrak{B})$ is in P, or otherwise
$\operatorname{CSP}(\mathfrak{B})$ is NP-complete.

Again, the easiest examples for structures satisfying the assumptions of
Theorem 1.4 come from $(\mathbb{Q},<)$ (see Section 4). The CSPs for first-
order reducts of $(\mathbb{Q},<)$ (see Section 2 for the definition of first-
order reduct) have been called _temporal CSPs_ and their computational
complexity has been classified [13]. There are many interesting polynomial-
time tractable temporal CSPs that have non-convex theories, which makes
temporal CSPs a particularly interesting class for understanding the situation
where the Nelson-Oppen conditions do not apply. Generic combinations of
temporal CSPs are isomorphic to first-order reducts of the _countable random
permutation_ introduced in [21] and studied in [27]; a complexity
classification of the CSPs of all reducts of the random permutation (as e.g.
in [13, 11, 25] for simpler structures than the random permutation) is out of
reach for the current methods. In principle, the method of canonical functions
(see [14]) can be applied but leads to a huge amount of cases and seems
combinatorially intractable at the moment.

###  1.4. Outline of the article

The rest of the article is organized as follows. In Section 2 we introduce
generic combinations, study existence and uniqueness and prove a result that
will help us to prove satisfiability of conjunctions of formulas. Afterwards,
in Section 3, we prove the main result about the computational complexity of
generic combinations of CSPs. In Section 4 we present examples for structures
with Property $J$ and for Theorem 1.4. Finally, in Section 5 we show that a
general complexity classification for all generic combinations is not
feasible.

##  2\. Generic Combinations

We already mentioned that our definition of CSPs for theories is a strict
generalisation of the notion of CSPs for structures, and this will be
clarified by the following proposition which is an immediate consequence of
Proposition 2.4.6 in [6].

######  Proposition 2.1.

Let $T$ be a first-order theory with finite relational signature. Then there
exists a structure $\mathfrak{B}$ such that
$\operatorname{CSP}(\mathfrak{B})=\operatorname{CSP}(T)$ if and only if $T$
has the _Joint Homomorphism Property (JHP)_ , that is, for any two models
$\mathfrak{A}$, $\mathfrak{B}$ of $T$ there exists a model $\mathfrak{C}$ of
$T$ such that both $\mathfrak{A}$ and $\mathfrak{B}$ homomorphically map to
$\mathfrak{C}$.

######  Example 2.2.

A simple example of two theories $T_{1},T_{2}$ with the JHP such that
$T_{1}\cup T_{2}$ does not have the JHP is given by

$\displaystyle T_{1}$ $\displaystyle\mathrel{\vcentcolon=}\\{\forall
x,y\;((O(x)\wedge O(y))\Rightarrow x=y)\\}$ $\displaystyle T_{2}$
$\displaystyle\mathrel{\vcentcolon=}\\{\forall x.\;\neg(P(x)\wedge Q(x))\\}$

Suppose for contradiction that $T_{1}\cup T_{2}$ has the JHP. Note that

$\displaystyle T_{1}\cup T_{2}\cup\\{\exists x(O(x)\wedge
P(x))\\}\quad\text{and }\quad T_{1}\cup T_{2}\cup\\{\exists y(O(y)\wedge
Q(y))\\}$

are satisfiable. The JHP implies that

$T_{1}\cup T_{2}\cup\\{\exists x(O(x)\wedge P(x)),\exists y(O(y)\wedge
Q(y))\\}$

has a model $\mathfrak{A}$, so $\mathfrak{A}$ has elements $u,v$ satisfying
$O(u)\wedge O(v)\wedge P(u)\wedge Q(v)$. Since $\mathfrak{A}\models T_{1}$ we
must have $u=v$, and so $\mathfrak{A}$ does not satisfy the sentence $\forall
x.\;\neg(P(x)\wedge Q(x))$ from $T_{2}$, a contradiction.

For general theories $T_{1},T_{2}$ even the question whether $T_{1}\cup T_{2}$
has the JHP might be a difficult question. But if both $T_{1}$ and $T_{2}$ are
$\omega$-categorical with a countably infinite model that _does not have
algebraicity_ , then $T_{1}\cup T_{2}$ always has the JHP (a consequence of
Lemma 2.5 below). A structure $\mathfrak{B}$ (and its first-order theory)
_does not have algebraicity_ if for all first-order formulas
$\phi(x_{0},x_{1},\dots,x_{n})$ and all elements $a_{1},\dots,a_{n}\in B$ the
set $\\{a_{0}\in B\mid\mathfrak{B}\models\phi(a_{0},a_{1},\dots,a_{n})\\}$ is
either infinite or contained in $\\{a_{1},\dots,a_{n}\\}$; otherwise, we say
that the structure _has algebraicity_.

Next, we will introduce _strong amalgamation_ which has a tight link to
algebraicity. The _age_ of a relational $\tau$-structure $\mathfrak{B}$ is the
class of all finite $\tau$-structures that embed into $\mathfrak{B}$. A class
$\mathcal{K}$ of structures has the _amalgamation property_ if for all
$\mathfrak{A},\mathfrak{B}_{1},\mathfrak{B}_{2}\in\mathcal{K}$ and embeddings
$f_{i}\colon\mathfrak{A}\rightarrow\mathfrak{B}_{i}$, for $i=1$ and $i=2$,
there exist $\mathfrak{C}\in\mathcal{K}$ and embeddings
$g_{i}\colon\mathfrak{B}_{i}\rightarrow\mathfrak{C}$ such that $g_{1}\circ
f_{1}=g_{2}\circ f_{2}$. It has the _strong amalgamation property_ if
additionally $g_{1}(B_{1})\cap g_{2}(B_{2})=g_{1}(f_{1}(A))=g_{2}(f_{2}(A))$.
If $\mathcal{K}$ is a class of structures with relational signature which is
closed under isomorphism, substructures, and has the amalgamation property,
then there exists an (up to isomorphism unique) countable homogeneous
structure $\mathfrak{B}$ whose age is $\mathcal{K}$. This structure
$\mathfrak{B}$ is called _Fraïssé-limit_ of $\mathcal{K}$ (see [24], page
326). Moreover, in this case, we have the following:

######  Proposition 2.3 ([24], p. 330).

If $\mathcal{K}$ is the age of a countable structure $\mathfrak{B}$, then
$\mathfrak{B}$ has no algebraicity if and only if $\mathcal{K}$ has the strong
amalgamation property.

The significance of strong amalgamation in the theory of combining decision
procedures has already been pointed out by Bruttomesso, Ghilardi, and Ranise
[19].

A structure $\mathfrak{B}_{1}$ is called a _reduct_ of a structure
$\mathfrak{B}_{2}$, and $\mathfrak{B}_{2}$ is called an _expansion_ of
$\mathfrak{B}_{1}$, if $\mathfrak{B}_{1}$ is obtained from $\mathfrak{B}_{2}$
by dropping some of the relations of $\mathfrak{B}_{1}$. If $\mathfrak{B}_{1}$
is a reduct of $\mathfrak{B}_{2}$ with the signature $\tau$ then we write
$\mathfrak{B}_{2}^{\tau}$ for $\mathfrak{B}_{1}$. An expansion
$\mathfrak{B}_{2}$ of $\mathfrak{B}_{1}$ is called a _first-order expansion_
if all additional relations in $\mathfrak{B}_{2}$ have a first-order
definition in $\mathfrak{B}_{1}$. A structure $\mathfrak{B}_{1}$ is called a
_first-order reduct_ if $\mathfrak{B}_{2}$ is a reduct of a first-order
expansion of $\mathfrak{B}_{2}$. Note that if a structure $\mathfrak{B}$ is
$2$-set-transitive then so is every first-order reduct of $\mathfrak{B}$
(since its automorphism group contains the automorphisms of $\mathfrak{B}$).

Let $\tau_{1}$ and $\tau_{2}$ be disjoint relational signatures, and let
${\mathcal{K}}_{i}$ be a class of isomorphism-closed finite
$\tau_{i}$-structures, for $i\in\\{1,2\\}$. Then
${\mathcal{K}}_{1}*{\mathcal{K}}_{2}$ denotes the class of
$(\tau_{1}\cup\tau_{2})$-structures given by
$\\{\mathfrak{A}\mid\mathfrak{A}^{\tau_{1}}\in\mathcal{K}_{1}\text{ and
}\mathfrak{A}^{\tau_{2}}\in\mathcal{K}_{2})\\}$.

If $\bar{a}=(a_{1},\dots,a_{n})\in B^{n}$ and $G$ is a permutation group on
$B$ then
$G\bar{a}\mathrel{\vcentcolon=}\\{(\alpha(a_{1}),\dots,\alpha(a_{n}))\mid\alpha\in
G\\}$ is called the _orbit_ of $\bar{a}$ (with respect to $G$); orbits of
pairs (i.e., $n=2$) are also called _orbitals_. Orbitals of pairs of equal
elements are called _trivial_. In this article, whenever we have a fixed
structure $\mathfrak{B}$ and not otherwise noted, $G$ will always be the
automorphisms group of $\mathfrak{B}$.

The following theorem is one of the most important tools when dealing with
$\omega$-categorical structures.

######  Theorem 2.4 (Engeler, Ryll-Nardzewski, Svenonius, see [24] p. 341).

Let $\mathfrak{B}$ be a countably infinite structure with countable signature.
Then, the following are equivalent:

  1. (1)

$\mathfrak{B}$ is $\omega$-categorical;

  2. (2)

for all $n\geq 1$ every orbit of $n$-tuples is first-order definable in
$\mathfrak{B}$;

  3. (3)

for all $n\geq 1$ there are only finitely many orbits of $n$-tuples.

Theorem 2.4 implies that a homogeneous structure with finite relational
signature is $\omega$-categorical, and the expansion of an
$\omega$-categorical structure by all first-order definable relations (i.e.,
all orbits of its age) is homogeneous. We are now ready to prove the first
result about generic combinations.

######  Lemma 2.5.

Let $T_{1}$ and $T_{2}$ be $\omega$-categorical theories with disjoint
relational signatures $\tau_{1}$ and $\tau_{2}$, with infinite models without
algebraicity. Then there exists an $\omega$-categorical model $\mathfrak{B}$
of $T_{1}\cup T_{2}$ without algebraicity such that

(1) $\displaystyle\text{ for all }k\in{\mathbb{N}},\bar{a},\bar{b}\in
B^{k}\text{ injective}\colon$
$\displaystyle\quad\operatorname{Aut}(\mathfrak{B}^{\tau_{1}})\bar{a}\cap\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})\bar{b}\neq\emptyset\quad\text{and}$
(2) $\displaystyle\text{ for all }k\in{\mathbb{N}},\bar{a}\in B^{k}\text{
injective}\colon$
$\displaystyle\quad\operatorname{Aut}(\mathfrak{B}^{\tau_{1}})\bar{a}\cap\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})\bar{a}=\operatorname{Aut}(\mathfrak{B})\bar{a}\,.$

###### Proof.

Let $\mathfrak{B}_{i}$ be a countably infinite model of $T_{i}$ without
algebraicity for $i=1$ and $i=2$. Consider the $\sigma_{i}$-expansion
$\mathfrak{C}_{i}$ of $\mathfrak{B}_{i}$ by all orbits of
$\operatorname{Aut}(\mathfrak{B}_{i})$, and choose the signatures of
$\mathfrak{C}_{1}$ and $\mathfrak{C}_{2}$ to be disjoint. Then, by definition,
$\mathfrak{C}_{i}$ is homogeneous and $\omega$-categorical and Theorem 2.4
implies that $\mathfrak{C}_{i}$ is first-order interdefinable with
$\mathfrak{B}_{i}$ and thus without algebraicity. Hence,
$\operatorname{Age}(\mathfrak{C}_{i})$ is a strong amalgamation class and
therefore,
$\mathcal{K}\mathrel{\vcentcolon=}\operatorname{Age}(\mathfrak{C}_{1})*\operatorname{Age}(\mathfrak{C}_{2})$
is a strong amalgamation class, too. Let $\mathfrak{C}$ be the Fraïssé-limit
of $\mathcal{K}$. By construction of $\mathfrak{C}$ two $n$-tuples $t$, $s$
are isomorphic over $\mathfrak{C}$ iff $t$ and $s$ satisfy the same $n$-ary
relations from $\mathfrak{C}_{1}$ and $\mathfrak{C}_{2}$. Therefore, there are
only finitely many non-isomorphic $n$-tuples over $\mathfrak{C}$, and hence,
homogeneity of $\mathfrak{C}$, there are only finitely many orbits of
$n$-tuples over $\mathfrak{C}$. This implies $\omega$-categoricity of
$\mathfrak{C}$. By strong amalgamation of $\mathcal{K}$ and Proposition 2.3,
$\mathfrak{C}$ has no algebraicity.

Hence, the $(\tau_{1}\cup\tau_{2})$-reduct $\mathfrak{B}$ of $\mathfrak{C}$ is
$\omega$-categorical and has no algebraicity. To show $(\ref{eq:free})$, let
$\bar{a},\bar{b}\in B^{k}$ be injective tuples and let $\mathfrak{A}$ be the
$(\sigma_{1}\cup\sigma_{2})$-structure with domain $A=\\{1,\dots,k\\}$ such
that $i\mapsto a_{i}$ is an embedding of $\mathfrak{A}$ into
$\mathfrak{C}^{\sigma_{1}}$ and $i\mapsto b_{i}$ is an embedding of
$\mathfrak{A}$ into $\mathfrak{C}^{\sigma_{2}}$. Then
$\mathfrak{A}\in\operatorname{Age}(\mathfrak{C})$, so there exists an
embedding $e\colon\mathfrak{A}\to\mathfrak{C}$. Let
$\bar{c}\mathrel{\vcentcolon=}(e(1),\dots,e(k))$. By the homogeneity of
$\mathfrak{C}^{\sigma_{i}}$ there exists
$\alpha_{i}\in\operatorname{Aut}(\mathfrak{C}^{\sigma_{i}})$ such that
$\alpha_{1}(\bar{c})=\bar{a}$ and $\alpha_{2}(\bar{c})=\bar{b}$, showing that
$\bar{c}\in\operatorname{Aut}(\mathfrak{B}^{\tau_{1}})\bar{a}\cap\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})\bar{b}$.
Finally, $(\ref{eq:splits})$ follows directly from the homogeneity of
$\mathfrak{C}$. ∎

Note that properties $(\ref{eq:free})$ and $(\ref{eq:splits})$ for
$\mathfrak{B}$, $\mathfrak{B}^{\tau_{1}}$, $\mathfrak{B}^{\tau_{2}}$ are
equivalent to items (1) and (2) in Section 1.1 for
$T=\operatorname{Th}(\mathfrak{B})$,
$T_{1}=\operatorname{Th}(\mathfrak{B}^{\tau_{1}})$,
$T_{2}=\operatorname{Th}(\mathfrak{B}^{\tau_{2}})$, respectively, because
$\mathfrak{B}$ is $\omega$-categorical. Lemma 2.5 motivates the following
definition.

######  Definition 2.6 (Generic Combination).

Let $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ be countably infinite
$\omega$-categorical structures with disjoint relational signatures $\tau_{1}$
and $\tau_{2}$, and let $\mathfrak{B}$ be a model of
$\operatorname{Th}(\mathfrak{B}_{1})\cup\operatorname{Th}(\mathfrak{B}_{2})$.
If $\mathfrak{B}$ satisfies item $(\ref{eq:free})$ then we say that
$\mathfrak{B}$ is a _free combination_ of $\mathfrak{B}_{1}$ and
$\mathfrak{B}_{2}$. If $\mathfrak{B}$ satisfies both item $(\ref{eq:free})$
and item $(\ref{eq:splits})$ then we say that $\mathfrak{B}$ is a _generic
combination_ (or _random combination_ ; see [1]) of $\mathfrak{B}_{1}$ and
$\mathfrak{B}_{2}$.

In later proofs we will need means to prove satisfiability of conjunctions of
formulas in the presence of parameters. This is facilitated by the following
lemma. For tuples $\bar{c}$ we will use
$\operatorname{Aut}_{\bar{c}}(\mathfrak{B})$ for
$\left\\{\alpha\in\operatorname{Aut}(\mathfrak{B})\mid\alpha(\bar{c})=\bar{c}\right\\}$.

######  Lemma 2.7.

Let $\mathfrak{B}$ be the generic combination of the structures
$\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ with relational signatures
$\tau_{1},\tau_{2}$ respectively. Let $B$ be the domain of $\mathfrak{B}$ and
$\bar{a},\bar{b}\in B^{n}$ injective tuples and $\bar{c}\in B^{m}$ such that
all entries of $\bar{c}$ are distinct from all entries of $\bar{a}$ and
$\bar{b}$. Then

(3)
$\displaystyle\operatorname{Aut}_{\bar{c}}(\mathfrak{B}^{\tau_{1}})\bar{a}\cap\operatorname{Aut}_{\bar{c}}(\mathfrak{B}^{\tau_{2}})\bar{b}\neq\emptyset\qquad\text{and}$
(4)
$\displaystyle\operatorname{Aut}_{\bar{c}}(\mathfrak{B}^{\tau_{1}})\bar{a}\cap\operatorname{Aut}_{\bar{c}}(\mathfrak{B}^{\tau_{2}})\bar{a}=\operatorname{Aut}_{\bar{c}}(\mathfrak{B})\bar{a}.$

###### Proof.

There exists
$\bar{d}\in\operatorname{Aut}(\mathfrak{B}^{\tau_{1}})(\bar{c},\bar{a})\cap\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})(\bar{c},\bar{b})$
by Property (1) of generic combination. Notice that we did not require
$\bar{c}$ to be injective. We can nevertheless apply Property (1) by removing
duplicate entries in $\bar{c}$, applying the property to the injective version
and reintroducing the duplicates afterwards. In particular,
$(d_{1},\dotsc,d_{m})\in\operatorname{Aut}(\mathfrak{B}^{\tau_{1}})\bar{c}\cap\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})\bar{c}=\operatorname{Aut}(\mathfrak{B})\bar{c}$
by Property (2) of generic combination. Hence, there exists
$\gamma\in\operatorname{Aut}(\mathfrak{B})$ such that
$\gamma((d_{1},\dotsc,d_{m}))=\bar{c}$. Furthermore, there exist
$\alpha\in\operatorname{Aut}(\mathfrak{B}^{\tau_{1}}),\beta\in\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})$
such that $\alpha((\bar{c},\bar{a}))=\bar{d}=\beta((\bar{c},\bar{b}))$. Hence,
$\gamma\circ\alpha\in\operatorname{Aut}_{\bar{c}}(\mathfrak{B}^{\tau_{1}})$
and $\gamma\circ\beta\in\operatorname{Aut}_{\bar{c}}(\mathfrak{B}^{\tau_{2}})$
and
$(\gamma\circ\alpha)\bar{a}=(\gamma\circ\beta)\bar{b}\in\operatorname{Aut}_{\bar{c}}(\mathfrak{B}^{\tau_{1}})\bar{a}\cap\operatorname{Aut}_{\bar{c}}(\mathfrak{B}^{\tau_{2}})\bar{b}$.

For equation (4), $\supseteq$ is trivial and $\subseteq$ is implied by
Property (2) of generic combination as follows. Let
$\bar{d}\in\operatorname{Aut}_{\bar{c}}(\mathfrak{B}^{\tau_{1}})\bar{a}\cap\operatorname{Aut}_{\bar{c}}(\mathfrak{B}^{\tau_{2}})\bar{a}$.
Then
$(\bar{c},\bar{d})\in\operatorname{Aut}(\mathfrak{B}^{\tau_{1}})(\bar{c},\bar{a})\cap\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})(\bar{c},\bar{a})$
and therefore
$(\bar{c},\bar{d})\in\operatorname{Aut}(\mathfrak{B})(\bar{c},\bar{a})$.
Hence, there exists $\gamma\in\operatorname{Aut}(\mathfrak{B})$ such that
$\gamma(\bar{c},\bar{a})=(\bar{c},\bar{d})$, i.e.,
$\bar{d}\in\operatorname{Aut}_{\bar{c}}(\mathfrak{B})\bar{a}$. ∎

Lemma 2.7 can be used to show the uniqueness of generic combinations.

######  Lemma 2.8.

Let $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ be countable
$\omega$-categorical relational structures. Then up to isomorphism, there is
at most one generic combination of $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$.

###### Proof.

Let $\mathfrak{B}$ and $\mathfrak{B}^{\prime}$ be two generic combinations of
$\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$. We prove that $\mathfrak{B}$ and
$\mathfrak{B}^{\prime}$ are isomorphic by a back-and-forth argument. For this,
we inductively extend a bijection $\alpha$ between finite subsets of
$\mathfrak{B}$ and $\mathfrak{B}^{\prime}$ such that $\alpha$ preserves all
first-order $\tau_{1}$-formulas and $\tau_{2}$-formulas. The empty map
$\alpha$ trivially preserves all first-order formulas. Both structures satisfy
the same first-order $\tau_{1}$-formulas without free variables and
$\tau_{2}$-formulas without free variables, since they are models of
$\operatorname{Th}(\mathfrak{B}_{1})\cup\operatorname{Th}(\mathfrak{B}_{2})$.
Now suppose that we have already constructed $\alpha$ for the finite
substructure of $\mathfrak{B}$ induced by the elements of the tuple
$\bar{b}\in B^{n}$ and want to extend $\alpha$ to another element $b_{n+1}$ of
$\mathfrak{B}$. By the $\omega$-categoricity of $T_{i}$, for $i=1$ and $i=2$,
there exists an element $c_{i}$ of $\mathfrak{B}^{\prime}$ such that
$(\bar{b},b_{n+1})$ satisfies the same formulas in $\mathfrak{B}^{\tau_{i}}$
as $(\alpha(\bar{b}),c_{i})$ satisfies in
$(\mathfrak{B}^{\prime})^{\tau_{i}}$. By Property (3) of Lemma 2.7 there
exists $c$ such that $(\alpha(\bar{b}),c)$ is in the same
$(\mathfrak{B}^{\prime})^{\tau_{i}}$ orbit as $(\alpha(\bar{b}),c_{i})$ for
$i=1$ and $i=2$. We define $\alpha(b_{n+1})\mathrel{\vcentcolon=}c$. Then,
$(\alpha(\bar{b}),b_{n+1})$ satisfies the same formulas in
$\mathfrak{B}^{\prime}$ as $(\bar{b},b_{n+1})$ satisfies in $\mathfrak{B}$ by
Condition (2) for generic combinations.

Extending $\alpha^{-1}$ to another element of $\mathfrak{B}^{\prime}$ is
symmetric. This concludes the back-and-forth construction of an isomorphism
between $\mathfrak{B}$ and $\mathfrak{B}^{\prime}$. ∎

Due to Lemma 2.8 we can now define $\mathfrak{B}_{1}\ast\mathfrak{B}_{2}$ as
_the_ generic combination of $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ for
structures $\mathfrak{B}_{1},\mathfrak{B}_{2}$ where a generic combination
exists.

We now prove Proposition 1.1 that we already stated in the introduction, and
which states that two countably infinite $\omega$-categorical structures with
disjoint relational signatures have a generic combination if and only if both
have no algebraicity, or at least one of the structures has an automorphism
group which is $n$-transitive for all $n\in{\mathbb{N}}$.

###### Proof of Proposition 1.1.

If both $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ do not have algebraicity
then the existence of an $\omega$-categorical generic combination follows from
Lemma 2.5. If on the other hand one of them, say $\mathfrak{B}_{1}$, is
$n$-transitive for all $n$ then $\mathfrak{B}_{1}$ is isomorphic to a first-
order reduct of $(\mathbb{N};=)$. The generic combination
$\mathfrak{B}_{1}\ast\mathfrak{B}_{2}$ can then easily be seen to be a first-
order expansion of $\mathfrak{B}_{2}$.

We prove the converse direction by contradiction. Let $\mathfrak{B}$ be the
generic combination of the $\tau_{1}$-structure $\mathfrak{B}_{1}$ and the
$\tau_{2}$-structure $\mathfrak{B}_{2}$. Recall that $\mathfrak{B}^{\tau_{i}}$
is isomorphic to $\mathfrak{B}_{i}$, for $i\in\\{1,2\\}$. By symmetry between
$\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$, we will assume towards a
contradiction that $\mathfrak{B}^{\tau_{1}}$ has algebraicity and
$\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})$ is not $n$-transitive for some
$n\in\mathbb{N}$. Choose $n$ to be smallest possible, so that
$\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})$ is not $n$-transitive. Therefore
there exist tuples $(b_{0},\dotsc,b_{n-1})$ and $(c_{0},\dotsc,c_{n-1})$ in
$B^{n}$, each with pairwise distinct entries, that are in different orbits
with respect to $\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})$. By the
minimality of $n$, there exists
$\alpha\in\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})$ such that
$\alpha(b_{1},\dots,b_{n-1})=(c_{1},\dots,c_{n-1})$. The algebraicity of
$\mathfrak{B}^{\tau_{1}}$ implies that there exists a first-order
$\tau_{1}$-formula $\phi(x_{0},x_{1},\dots,x_{m})$ and pairwise distinct
elements $a_{1},\dots,a_{m}$ of $B$ such that $\phi(x,a_{1},\dots,a_{m})$
holds for precisely one element $a_{0}$ other than $a_{1},\dots,a_{m}$. By
adding unused extra variables to $\phi$ we can assume that $m\geq n-1$. Choose
elements $b_{n},\dotsc,b_{m}$ of $B$ such that the entries of
$(b_{0},\dotsc,b_{n-1},b_{n},\dotsc,b_{m})$ are pairwise distinct and define
$c_{i}\mathrel{\vcentcolon=}\alpha(b_{i})$ for
$i\in\left\\{n,\dotsc,m\right\\}$. Since $\mathfrak{B}$ is a free combination,
there exist tuples
$(b_{0}^{\prime},\dotsc,b_{m}^{\prime}),\,(c_{0}^{\prime},\dotsc,c_{m}^{\prime})$
and $\beta_{1},\gamma_{1}\in\operatorname{Aut}(\mathfrak{B}^{\tau_{1}})$ and
$\beta_{2},\gamma_{2}\in\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})$ such that

$\displaystyle\beta_{2}(b_{0},\dotsc,b_{m})=(b_{0}^{\prime},\dotsc,b_{m}^{\prime}),$
$\displaystyle\qquad\beta_{1}(b_{0}^{\prime},\dotsc,b_{m}^{\prime})=(a_{0},\dotsc,a_{m}),$
$\displaystyle\gamma_{2}(c_{0},\dotsc,c_{m})=(c_{0}^{\prime},\dotsc,c_{m}^{\prime}),$
$\displaystyle\qquad\gamma_{1}(c_{0}^{\prime},\dotsc,c_{m}^{\prime})=(a_{0},\dotsc,a_{m}).$

Because
$\gamma_{1}^{-1}\circ\beta_{1}\in\operatorname{Aut}(\mathfrak{B}^{\tau_{1}})$
and
$\gamma_{2}\circ\alpha\circ\beta_{2}^{-1}\in\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})$
both map $(b_{1}^{\prime},\dotsc,b_{m}^{\prime})$ to
$(c_{1}^{\prime},\dotsc,c_{m}^{\prime})$, and due to Condition (2) for generic
combinations, there exists $\mu\in\operatorname{Aut}(\mathfrak{B})$ such that
$\mu(b_{1}^{\prime},\dotsc,b_{m}^{\prime})=(c_{1}^{\prime},\dotsc,c_{m}^{\prime})$.
Since any operation in $\operatorname{Aut}(\mathfrak{B}^{\tau_{1}})$ preserves
$\phi$, we have
$\gamma_{1}\circ\mu\circ\beta_{1}^{-1}(a_{0},\dots,a_{m})=(a_{0},\dots,a_{m})$.
Therefore $\mu$ must map $b_{0}^{\prime}$ to $c_{0}^{\prime}$. Hence,
$\gamma_{2}^{-1}\circ\mu\circ\beta_{2}\in\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})$
maps $(b_{0},\dotsc,b_{n-1})$ to $(c_{0},\dotsc,c_{n-1})$, contradicting our
assumption that they lie in different orbits with respect to
$\operatorname{Aut}(\mathfrak{B}^{\tau_{2}})$. ∎

##  3\. On the Necessity of the Nelson-Oppen Conditions

In this section we prove that for theories with Property $J$ the conditions of
Nelson and Oppen are not only sufficient, but also necessary for the
polynomial-time tractability of generic combinations (unless P = NP). In
particular, we prove Theorem 1.4 from the introduction. In order to avoid an
excess of superscripts we will drop the bar above tuples in this section. We
need the following characterisation of convexity of $\omega$-categorical
theories.

######  Theorem 3.1 (Lemma 6.1.3 in [6]).

Let $\mathfrak{B}$ be a countably infinite $\omega$-categorical relational
structure and let $T$ be its first-order theory. Then the following are
equivalent.

  * •

$T$ is convex;

  * •

$\mathfrak{B}$ has a binary injective polymorphism.

Moreover, if $\mathfrak{B}$ contains the relation $\neq$, these conditions are
also equivalent to the following.

  * •

If $S$ is a finite set of atomic $\tau$-formulas such that $S\cup
T\cup\\{x_{1}\neq y_{1}\\}$ is satisfiable and $S\cup T\cup\\{x_{2}\neq
y_{2}\\}$ is satisfiable, then $T\cup S\cup\\{x_{1}\neq y_{1},x_{2}\neq
y_{2}\\}$ is satisfiable, too.

The construction of the binary injective polymorphism, which is at the core of
this theorem, first finds an injective homomorphism from a finite substructure
of $\mathfrak{B}^{2}$ to $\mathfrak{B}$ and then uses compactness of first-
order logic to expand its domain to $\mathfrak{B}^{2}$.

An operation $f\colon B^{k}\to B$ is called _essentially unary_ if there
exists an $i\leq k$ and a function $g\colon B\to B$ such that
$f(x_{1},\dots,x_{k})=g(x_{i})$ for all $x_{1},\dots,x_{k}\in B$. The
operation $f$ is called _essential_ if it is not essentially unary. Hence, if
a function $f\colon B^{2}\rightarrow B$ is essential then there exist
$p,q,r,s\in B^{2}$ such that $p_{2}=q_{2}$ and $r_{1}=s_{1}$ and
$f(p_{1},p_{2})\neq f(q_{1},q_{2})$ and $f(r_{1},r_{2})\neq f(s_{1},s_{2})$.
The tuples $(p,q)$ and $(r,s)$ are called _witnesses_ for the essentiality of
$f$.

The following fact is well-known. We give a short proof to illustrate how it
follows from known results.

######  Proposition 3.2.

Let $\mathfrak{B}$ be an infinite $\omega$-categorical structure with finite
relational signature containing the relation $\neq$ and such that all
polymorphisms of $\mathfrak{B}$ are essentially unary. Then
$\operatorname{CSP}(\mathfrak{B})$ is NP-hard.

###### Proof.

Let $E$ be the set of all relations (on the domain of $\mathfrak{B}$) that
have a first-order definition over the empty signature. If all polymorphisms
of $\mathfrak{B}$ are essentially unary and preserve $\neq$, they preserve all
relations in $E$. Therefore, all relations in $E$ are pp-definable in
$\mathfrak{B}$ (see [15], Theorem 4). In this case, there is a finite
signature reduct of $\mathfrak{B}$ which has an NP-hard CSP (see [12], Theorem
1). ∎

Hence, it suffices to show that the existence of an essential polymorphism of
the generic combination of two countably infinite $\omega$-categorical
structures $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ implies the existence of
a binary injective polymorphism. The key technical result is the following
proposition.

######  Proposition 3.3.

Let $\mathfrak{B}$ be the generic combination of two $\omega$-categorical
relational structures $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ such that the
following holds:

  * •

$\mathfrak{B}$ has a binary essential polymorphism,

  * •

both $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ are without algebraicity,

  * •

$\mathfrak{B}_{1}$ can prevent crosses,

  * •

$\mathfrak{B}_{2}$ is 2-set-transitive and $\neq$ is pp-definable in
$\mathfrak{B}_{2}$.

Then $\mathfrak{B}_{2}$ has a binary injective polymorphism.

To make the technical part of the proof of Proposition 3.3 more accessible and
clarify which condition is needed where, we will break it into two lemmata.

######  Lemma 3.4.

Let $\mathfrak{B}$ be the generic combination of two $\omega$-categorical
relational structures $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$. Let
$\mathfrak{B}_{1}$ be a structure which can prevent crosses and without
algebraicity and let
$\varphi(x_{1},x_{2},x_{1}^{\prime},y_{1},y_{2},y_{2}^{\prime};a)$ be a first-
order formula over $\mathfrak{B}_{2}$ with parameter tuple $a$ such that there
exists a solution $s$ for $\varphi$ which is injective and the image of $s$
does not contain any value from $a$. Then, for any binary polymorphism
$f\in\operatorname{Pol}(\mathfrak{B}_{1})$ there exist
$x_{1},x_{2},x_{1}^{\prime},y_{1},y_{2},y_{2}^{\prime}$ such that

(5)
$\varphi(x_{1},x_{2},x_{1}^{\prime},y_{1},y_{2},y_{2}^{\prime},a)\operatorname{\wedge}\big{(}f(x_{1},x_{2})\neq
f(x_{1}^{\prime},x_{2})\operatorname{\vee}f(y_{1},y_{2})\neq
f(y_{1},y_{2}^{\prime})\big{)}.$

###### Proof.

Let $\theta$ be a cross prevention formula of $\mathfrak{B}_{1}$. Define
$\rho(x_{1},x_{2},x_{1}^{\prime},y_{1},y_{2},y_{2}^{\prime})\mathrel{\vcentcolon\equiv}\theta(x_{1},x_{1}^{\prime},y_{1},y_{1})\operatorname{\wedge}\theta(x_{2},x_{2},y_{2},y_{2}^{\prime})$.
Because $\mathfrak{B}_{1}$ is without algebraicity and there are injective
solutions for $\theta(x_{1},x_{1}^{\prime},y_{1},y_{1})$ and
$\theta(x_{2},x_{2},y_{2},y_{2}^{\prime})$ we can use Neumann’s lemma (see
Corollary 4.2.2 in [24]) to find a solution $t_{1}$ for $\rho$ that is
injective and avoids all entries in $a$ in its image. Hence, there are
injective solutions $t_{1},t_{2}$ for $\rho,\varphi$ respectively that avoid
all values in $a$ in their image and therefore Lemma 2.7 is applicable and
there exists a solution $t$ for $\rho\operatorname{\wedge}\varphi$.
We now look at the images of $f$:

$\displaystyle f(t(x_{1}),t(x_{2}))$ $\displaystyle=x$ $\displaystyle
f(t(x_{1}^{\prime}),t(x_{2}))$ $\displaystyle=x^{\prime}$ $\displaystyle
f(t(y_{1}),t(y_{2}))$ $\displaystyle=y$ $\displaystyle
f(t(y_{1}),t(y_{2}^{\prime}))$ $\displaystyle=y^{\prime}$

As $f$ is a polymorphism of $\mathfrak{B}_{1}$ the tuple
$(x,x^{\prime},y,y^{\prime})$ must satisfy $\theta$. Hence, either $x\neq
x^{\prime}$ or $y\neq y^{\prime}$. ∎

######  Lemma 3.5.

Let $\mathfrak{B}$ be the generic combination of two $\omega$-categorical
relational structures $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$, both of which
are without algebraicity. Furthermore, assume that $\mathfrak{B}_{1}$ can
prevent crosses and that $\mathfrak{B}_{2}$ is 2-set-transitive. Let $B$ be
the domain of $\mathfrak{B}$ and choose $a,b,c,d\in B^{2}$ such that
$a_{1}\neq b_{1},\,a_{2}=b_{2}$ and $c_{1}=d_{1},c_{2}\neq d_{2}$.

Then, for any binary essential polymorphism
$f\in\operatorname{Pol}(\mathfrak{B}_{1})$ there exist
$\tilde{a},\tilde{b},\tilde{c},\tilde{d}\in B^{2}$ such that
$f(\tilde{a}_{1},\tilde{a}_{2})\neq f(\tilde{b}_{1},\tilde{b}_{2})$ and
$f(\tilde{c}_{1},\tilde{c}_{2})\neq f(\tilde{d}_{1},\tilde{d}_{2})$ and
$(\tilde{a}_{i},\tilde{b}_{i},\tilde{c}_{i},\tilde{d}_{i})\in\operatorname{Aut}(\mathfrak{B}_{2})(a_{i},b_{i},c_{i},d_{i})$
for $i=1$ and $i=2$.

$c_{1}$$a_{1}$$b_{1}$$r_{1}$$O_{1}$$\tilde{c}_{1}$$p_{1}$$q_{1}$$O_{1}$$a_{2}$$c_{2}$$d_{2}$$p_{2}$$O_{2}$$\tilde{a}_{2}$$r_{2}$$s_{2}$$O_{2}$$a$$b$$p$$q$$c$$d$$r$$s$
Figure 2. An illustration of Case 1 in the proof of Lemma 3.5. Dashed edges
indicate (potential) disequalities between function values.

###### Proof.

Case 1: Both $(c_{1},a_{1},b_{1})$ and $(a_{2},c_{2},d_{2})$ are injective
tuples (see Figure 2).

Define
$O_{1}\mathrel{\vcentcolon=}\operatorname{Aut}(\mathfrak{B}_{2})(c_{1},a_{1},b_{1})$
and
$O_{2}\mathrel{\vcentcolon=}\operatorname{Aut}(\mathfrak{B}_{2})(a_{2},c_{2},d_{2})$.
Notice that $O_{1}$ and $O_{2}$ can be defined by first-order formulas because
$\mathfrak{B}_{2}$ is $\omega$-categorical. We start by using one of the
witnesses of essentiality of $f$ that is guaranteed to exist by definition,
i.e., $p,q\in B^{2}$ such that $f(p_{1},p_{2})\neq f(q_{1},q_{2})$ with
$p_{2}=q_{2}$. Due to 2-set-transitivity, we can assume that there exists
$\alpha\in\operatorname{Aut}(\mathfrak{B}_{2})$ such that
$\alpha(p_{1})=a_{1}$ and $\alpha(q_{1})=b_{1}$ (otherwise, swap $p$ and $q$).
Now look at all $\tilde{c}_{1}\in B$ such that $(\tilde{c}_{1},p_{1},q_{1})\in
O_{1}$. If for
$\tilde{a}\mathrel{\vcentcolon=}p,\,\tilde{b}\mathrel{\vcentcolon=}q$ there
are $\tilde{c}_{2},\,\tilde{d}_{2}$ such that
$(\tilde{a},\tilde{b},\tilde{c},\,\tilde{d})$ is a witness for the statement
of the lemma, we are done. Otherwise, for all
$\tilde{c}_{1},\tilde{c}_{2},\tilde{d}_{2}\in B$ the following holds:

$(\tilde{c}_{1},p_{1},q_{1})\in
O_{1}\operatorname{\wedge}(p_{2},\tilde{c}_{2},\tilde{d}_{2})\in
O_{2}\Rightarrow
f(\tilde{c}_{1},\tilde{c}_{2})=f(\tilde{c}_{1},\tilde{d}_{2})$

In this case we consider the second witness of essentiality of $f$ guaranteed
to exist by definition, i.e., $r,s\in B^{2}$ with $f(r_{1},r_{2})\neq
f(s_{1},s_{2})$ and $r_{1}=s_{1}$. Again due to 2-set-transitivity, there
exists $\beta\in\operatorname{Aut}(\mathfrak{B}_{2})$ such that
$\beta(r_{2})=c_{2}$ and $\beta(s_{2})=d_{2}$ (otherwise swap $r$ and $s$).
Assume now, that for all $\tilde{a}_{1},\tilde{b}_{1},\tilde{a}_{2}\in B$ the
following holds:

(6) $(r_{1},\tilde{a}_{1},\tilde{b}_{1})\in
O_{1}\operatorname{\wedge}(\tilde{a}_{2},r_{2},s_{2})\in O_{2}\Rightarrow
f(\tilde{a}_{1},\tilde{a}_{2})=f(\tilde{b}_{1},\tilde{a}_{2}).$

We now argue why we can apply Lemma 3.4 to

$\displaystyle\phi(x_{1},x_{2},x_{1}^{\prime},y_{1},y_{2},y_{2}^{\prime};p_{1},p_{2},q_{1},r_{1},r_{2},s_{2})\mathrel{\vcentcolon\equiv}$
$\displaystyle\,(y_{1},p_{1},q_{1})\in
O_{1}\operatorname{\wedge}(p_{2},y_{2},y^{\prime}_{2})\in
O_{2}\operatorname{\wedge}$ $\displaystyle\,(r_{1},x_{1},x^{\prime}_{1})\in
O_{1}\operatorname{\wedge}(x_{2},r_{2},s_{2})\in O_{2},$

where $p,q,r,s$ are parameters. Define the set
$T\mathrel{\vcentcolon=}\left\\{y_{1}\mid(y_{1},p_{1},q_{1})\in
O_{1}\right\\}$. $T$ is non-empty because there is an automorphism $\alpha$
such that $\alpha(p_{1})=a_{1}$ and $\alpha(q_{1})=b_{1}$ and hence
$\alpha^{-1}(c_{1})\in T$. Furthermore, $a_{1}\neq c_{1}\neq b_{1}$ and hence
$p_{1}\neq\alpha^{-1}(c_{1})\neq q_{1}$. Therefore, $T$ is infinite because
$\mathfrak{B}_{2}$ has no algebraicity. In a similar way, when considering all
solutions for any other conjunct of $\phi$, each variable can take infinitely
many values. For the two conjuncts with two free variables Neumann’s lemma
guarantees the existence of infinitely many tuples with pairwise distinct
entries in the orbit. Therefore, $\phi$ is a first-order formula with
parameters in $\mathfrak{B}_{2}$ which has an injective solution without any
of the parameter values in its image.

An application of Lemma 3.4 yields that Implication (6) must be false. Hence,
there are $\tilde{a}_{1},\tilde{b}_{1},\tilde{a}_{2}\in B$ such that
$(r_{1},\tilde{a}_{1},\tilde{b}_{1})\in O_{1}$ and
$(\tilde{a}_{2},r_{2},s_{2})\in O_{2}$ and $f(\tilde{a}_{1},\tilde{a}_{2})\neq
f(\tilde{b}_{1},\tilde{a}_{2})$. Together with
$\tilde{c}\mathrel{\vcentcolon=}r$ and $\tilde{d}\mathrel{\vcentcolon=}s$, the
points $\tilde{a},\tilde{b},\tilde{c},\tilde{d}$ satisfy all conditions from
the statement.

$a_{1},c_{1}$$b_{1}$$a_{2}$$c_{2}$$d_{2}$$a$$b$$c$$d$

$a_{1},c_{1}$$b_{1}$$a_{2}$$c_{2}$$d_{2}$$a$$b$$c$$d$

Figure 3. An illustration of the subcases of Case 2 (up to permutation of
variables) in the proof of Lemma 3.5. Dashed edges indicate (potential)
disequalities between function values.

Case 2: $(c_{1},a_{1},b_{1})$ or $(a_{2},c_{2},d_{2})$ are not injective,
i.e., $c_{1}=a_{1}$ or $c_{1}=b_{1}$ or $a_{2}=c_{2}$ or $a_{2}=d_{2}$ (see
Figure 3).

In this case, the witnesses can be constructed using Case 1 by starting with
suitable injective tuples. If $c_{1}=a_{1}$ we consider a new tuple
$(c^{\prime}_{1},a^{\prime}_{1},b^{\prime}_{1})$ which is injective such that
the $\mathfrak{B}_{2}$ orbits of $(c_{1},b_{1})$,
$(c^{\prime}_{1},a^{\prime}_{1})$ and $(c^{\prime}_{1},b^{\prime}_{1})$ are
the same (for $c_{1}=b_{1}$ we do the same but with the $\mathfrak{B}_{2}$
orbit of $(c_{1},a_{1})$ instead of $(c_{1},b_{1})$). This tuple exists due to
no-algebraicity of $\mathfrak{B}_{2}$. Likewise, if $a_{2}=c_{2}$ we can find
$(a^{\prime}_{2},c^{\prime}_{2},d^{\prime}_{2})$ injective such that the
$\mathfrak{B}_{2}$ orbits of $(a_{2},d_{2})$,
$(a^{\prime}_{2},c^{\prime}_{2})$ and $(a^{\prime}_{2},d^{\prime}_{2})$ are
the same (for $a_{2}=d_{2}$ we use the $\mathfrak{B}_{2}$ orbit of
$(a_{2},c_{2})$ instead of $(a_{2},d_{2})$). If $(c_{1},a_{1},b_{1})$ or
$(a_{2},c_{2},d_{2})$ was injective already, we keep this tuple but name them
$a_{i}^{\prime}$ etc. to simplify the presentation.

Now, we can apply Case 1 to $(c^{\prime}_{1},a^{\prime}_{1},b^{\prime}_{1})$
and $(a^{\prime}_{2},c^{\prime}_{2},d^{\prime}_{2})$ to find
$\tilde{a}^{\prime},\tilde{b}^{\prime},\tilde{c}^{\prime},\tilde{d}^{\prime}\in
B^{2}$ as promised by this lemma.

For $c_{1}=a_{1}$ both
$(\tilde{c}^{\prime}_{1},\tilde{a}^{\prime}_{1},\tilde{c}^{\prime}_{1},\tilde{c}^{\prime}_{1})$
and
$(\tilde{c}^{\prime}_{1},\tilde{b}^{\prime}_{1},\tilde{c}^{\prime}_{1},\tilde{c}^{\prime}_{1})$
are in the same orbit as $(a_{1},b_{1},c_{1},d_{1})$ because
$(\tilde{c}^{\prime}_{1},\tilde{a}^{\prime}_{1}),(\tilde{c}^{\prime}_{1},\tilde{b}^{\prime}_{1})$
and $(c_{1},b_{1})$ have the same orbit and $a_{1}=c_{1}=d_{1}$. Likewise for
$a_{2}=c_{2}$ in the second coordinate, both
$(\tilde{a}^{\prime}_{2},\tilde{a}^{\prime}_{2},\tilde{a}^{\prime}_{2},\tilde{d}^{\prime}_{2})$
and
$(\tilde{a}^{\prime}_{2},\tilde{a}^{\prime}_{2},\tilde{a}^{\prime}_{2},\tilde{c}^{\prime}_{2})$
are in the same orbit as $(a_{2},b_{2},c_{2},d_{2})$.

However, if $f(\tilde{a}^{\prime}_{1},\tilde{a}^{\prime}_{2})\neq
f(\tilde{b}^{\prime}_{1},\tilde{a}^{\prime}_{2})$ then either
$f(\tilde{a}^{\prime}_{1},\tilde{a}^{\prime}_{2})\neq
f(\tilde{c}^{\prime}_{1},\tilde{a}^{\prime}_{2})$ or
$f(\tilde{b}^{\prime}_{1},\tilde{a}^{\prime}_{2})\neq
f(\tilde{c}^{\prime}_{1},\tilde{a}^{\prime}_{2})$. Likewise, either
$f(\tilde{c}^{\prime}_{1},\tilde{a}^{\prime}_{2})\neq
f(\tilde{c}^{\prime}_{1},\tilde{c}^{\prime}_{2})$ or
$f(\tilde{c}^{\prime}_{1},\tilde{a}^{\prime}_{2})\neq
f(\tilde{c}^{\prime}_{1},\tilde{d}^{\prime}_{2})$. Therefore, there is a tuple
$(a^{\prime},b^{\prime},c^{\prime},d^{\prime})=((a_{1}^{\prime},b_{1}^{\prime},c_{1}^{\prime},d_{1}^{\prime}),(a_{2}^{\prime},b_{2}^{\prime},c_{2}^{\prime},d_{2}^{\prime}))$
in

$\left\\{(\tilde{c}^{\prime}_{1},\tilde{a}^{\prime}_{1},\tilde{c}^{\prime}_{1},\tilde{c}^{\prime}_{1}),\,(\tilde{c}^{\prime}_{1},\tilde{b}^{\prime}_{1},\tilde{c}^{\prime}_{1},\tilde{c}^{\prime}_{1})\right\\}\times\left\\{(\tilde{a}^{\prime}_{2},\tilde{a}^{\prime}_{2},\tilde{a}^{\prime}_{2},\tilde{c}^{\prime}_{2}),\,(\tilde{a}^{\prime}_{2},\tilde{a}^{\prime}_{2},\tilde{a}^{\prime}_{2},\tilde{d}^{\prime}_{2})\right\\},$

which satisfies the lemma.

The procedure is analogous for other identifications. ∎

Notice that Lemma 3.5 also holds for polymorphisms of $\mathfrak{B}$ because
$\operatorname{Pol}(\mathfrak{B})\subseteq\operatorname{Pol}(\mathfrak{B}_{1})$.
We are now ready to prove Proposition 3.3.

###### Proof of Proposition 3.3.

Let $\phi$ be a (finite) conjunction of atomic formulas over
$\mathfrak{B}_{2}$ such that $\phi\operatorname{\wedge}x\neq y$ and
$\phi\operatorname{\wedge}u\neq v$ are satisfiable and $s_{1},\,s_{2}$ are
satisfying assignments respectively. As $\mathfrak{B}_{2}$ is
$\omega$-categorical and $\neq$ is pp-definable in $\mathfrak{B}_{2}$, Theorem
3.1 is applicable. Hence, it is sufficient to prove satisfiability of
$\phi\operatorname{\wedge}x\neq y\operatorname{\wedge}u\neq v$ in
$\mathfrak{B}_{2}$. Let $f\in\operatorname{Pol}(\mathfrak{B})$ be a binary
essential polymorphism. If $s_{1}(u)\neq s_{1}(v)$ or $s_{2}(x)\neq s_{2}(y)$
we have found a satisfying assignment for $\phi\operatorname{\wedge}x\neq
y\operatorname{\wedge}u\neq v$, which is what we wanted. Otherwise, due to
Lemma 3.5 above, there are witnesses
$\tilde{x},\,\tilde{y},\tilde{u},\tilde{v}\in B^{2}$ of essentiality of $f$
such that $(\tilde{x}_{1},\tilde{y}_{1},\tilde{u}_{1})$ is in the same
$\mathfrak{B}_{2}$ orbit as $s_{1}(x,y,u)$ and
$(\tilde{x}_{2},\tilde{u}_{2},\tilde{v}_{2})$ is in the same
$\mathfrak{B}_{2}$ orbit as $s_{2}(x,u,v)$. Hence, there exist automorphisms
$\alpha_{1},\alpha_{2}\in\operatorname{Aut}(\mathfrak{B}_{2})$, such that

$\displaystyle f(\alpha_{1}(s_{1}(x)),\alpha_{2}(s_{2}(x)))$
$\displaystyle=f(\tilde{x}_{1},\tilde{x}_{2})$ $\displaystyle\neq
f(\tilde{y}_{1},\tilde{x}_{2})$
$\displaystyle=f(\alpha_{1}(s_{1}(y)),\alpha_{2}(s_{2}(x)))$
$\displaystyle=f(\alpha_{1}(s_{1}(y)),\alpha_{2}(s_{2}(y)))\quad\text{and}$
$\displaystyle f(\alpha_{1}(s_{1}(u)),\alpha_{2}(s_{2}(u)))$
$\displaystyle=f(\tilde{u}_{1},\tilde{u}_{2})$ $\displaystyle\neq
f(\tilde{u}_{1},\tilde{v}_{2})$
$\displaystyle=f(\alpha_{1}(s_{1}(u)),\alpha_{2}(s_{2}(v)))$
$\displaystyle=f(\alpha_{1}(s_{1}(v)),\alpha_{2}(s_{2}(v))).$

Therefore, $z\mapsto f((\alpha_{1}\circ s_{1})(z),(\alpha_{2}\circ s_{2})(z))$
for any variable $z$ that occurs in $\phi\operatorname{\wedge}x\neq
y\operatorname{\wedge}u\neq v$ is a solution for
$\phi\operatorname{\wedge}x\neq y\operatorname{\wedge}u\neq v$. ∎

To apply Proposition 3.3, we need to prove the existence of binary essential
polymorphisms of generic combinations $\mathfrak{B}$. For this, we use an idea
that first appeared in [13] and was later generalized in [6], based on the
following concept. A permutation group $G$ on a set $B$ has the _orbital
extension property (OEP)_ if there is an orbital $O$ such that for all
$b_{1},b_{2}\in B$ there is an element $c\in B$ where $(b_{1},c)\in O$ and
$(b_{2},c)\in O$. Notice that such $c$ must always be distinct from $b_{1}$
and $b_{2}$. The relevance of the OEP comes from the following lemma.

######  Lemma 3.6 (Kára’s Lemma; see [6], Lemma 5.3.10).

Let $\mathfrak{B}$ be a structure with an essential polymorphism and an
automorphism group with the OEP. Then $\mathfrak{B}$ must have a binary
essential polymorphism.

To apply this lemma to the generic combination $\mathfrak{B}$ of
$\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$, we have to verify that
$\operatorname{Aut}(\mathfrak{B})$ has the OEP.

######  Lemma 3.7.

Any 2-set-transitive permutation group on a set with at least 4 elements has
the OEP.

###### Proof.

Let $G$ be a 2-set-transitive permutation group on a set $B$. If $G$ is even
2-transitive then the statement is obvious. Otherwise, observe that there are
exactly two orbitals $O$ and $P$ such that $x\neq y$ if and only if $(x,y)\in
O$ and $(y,x)\in P$. Let $b_{1},b_{2}\in B$ be distinct. Consider the
tournament induced on $B$ by the edge relation $O$ and let
$(\left\\{x,y,u,v\right\\};O)$ be any 4-element substructure of $(B;O)$. There
exists a node in $\left\\{x,y,u,v\right\\}$, say $x$, with two incoming edges,
say $(y,x),(u,x)\in O$. By 2-set-transitivity there exists $\alpha\in G$ such
that $\alpha(\left\\{b_{1},b_{2}\right\\})=\left\\{y,u\right\\}$. Choose
$c\mathrel{\vcentcolon=}\alpha^{-1}(x)$ and we get $(b_{1},c),(b_{2},c)\in O$.
∎

######  Lemma 3.8.

Let $\mathfrak{B}$ be a generic combination of two $\omega$-categorical
relational structures $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ with the OEP.
Then $\mathfrak{B}$ has the OEP.

###### Proof.

For $i=1$ and $i=2$, let $O_{i}$ be the orbital that witnesses the OEP in
$\mathfrak{B}_{i}$. Then $P\mathrel{\vcentcolon=}O_{1}\cap O_{2}$ is an
orbital in $\mathfrak{B}$, and we claim that it witnesses the OEP in
$\mathfrak{B}$. Let $b_{1},b_{2}$ be elements of $\mathfrak{B}$. Choose
$c_{i}$ such that $(b_{1},c_{i})\in O_{i}$ and $(b_{2},c_{i})\in O_{i}$ for
$i=1$ and $i=2$. Because $c_{1},c_{2}$ will be distinct from $b_{1},b_{2}$,
Lemma 2.7 yields that there exists
$c\in\operatorname{Aut}_{b_{1},b_{2}}(\mathfrak{B}_{1})c_{1}\cap\operatorname{Aut}_{b_{1},b_{2}}(\mathfrak{B}_{2})c_{2}$,
which implies $(b_{1},c)\in P$ and $(b_{2},c)\in P$. ∎

Finally, we prove Theorem 1.4. Property $J$ from Definition 1.3 is needed in
order to apply Proposition 3.3 twice.

###### Proof of Theorem 1.4.

If all polymorphisms of $\mathfrak{B}$ are essentially unary then Proposition
3.2 shows that $\operatorname{CSP}(\mathfrak{B})$ is NP-hard. Otherwise,
$\mathfrak{B}$ has a binary essential polymorphism by Lemma 3.6, because
$\mathfrak{B}$ has the OEP by Lemma 3.7 and Lemma 3.8. Property $J$ states
that $\mathfrak{B}_{i}$, for $i=1$ and $i=2$, is 2-set-transitive, contains a
binary relation symbol that denotes $\neq$ and is without algebraicity. This
implies that $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ satisfy the assumptions
of Proposition 3.3. It follows that $\mathfrak{B}_{1}$ has a binary injective
polymorphism. By Theorem 3.1, this shows that
$\operatorname{Th}(\mathfrak{B}_{1})$ is convex.

By symmetry also $\operatorname{Th}(\mathfrak{B}_{2})$ is convex. Now, the
Nelson-Oppen combination procedure implies that
$\operatorname{CSP}(\mathfrak{B})$ is in P. ∎

##  4\. Examples

We will now present examples of structures with Property $J$.

######  Example 4.1.

All first-order expansions of $(\mathbb{Q};\neq,<)$ have Property $J$. It is
easy to check that $(\mathbb{Q};<)$ is 2-set transitive, $\omega$-categorical
and without algebraicity. These properties are generally preserved when
expanding a structure with first-order definable relations. A cross prevention
formula for these structures is

$\phi(x,y,u,v)\mathrel{\vcentcolon\equiv}x<v\operatorname{\wedge}y>u.$

Furthermore, all polynomial-time tractable first-order expansions of
$(\mathbb{Q};<)$ are known (see [13]) and there exist tractable expansions
which are not convex. One such structure is
$({\mathbb{Q}};\neq,\leq,R_{\operatorname{mi}})$ with

$R_{\operatorname{mi}}\mathrel{\vcentcolon=}\\{(x,y,z)\in{\mathbb{Q}}^{3}\mid
x\geq y\vee x>z\\}.$

######  Example 4.2.

Let $C$ be the binary branching homogeneous $C$-relation on a countably
infinite set [10]. The computational complexity of the $\operatorname{CSP}$s
of all first-order expansions of this structure has been fully classified in
[11]. All these first-order expansions (some of which are polynomial-time
tractable) have Property $J$. Here, a cross prevention formula is
$\phi(x,y,u,v)\mathrel{\vcentcolon\equiv}\exists
a\big{(}C(x,u;a)\operatorname{\wedge}C(y,a;v)\big{)}$.

Furthermore, we can describe a large family of structures with Property $J$:

######  Lemma 4.3.

Let $\mathfrak{B}$ be a countably infinite homogeneous relational structure
with finitely many relations, each of arity at least 3 where each tuple in
every relation of $\mathfrak{B}$ has pairwise distinct entries. Then
$\mathfrak{B}$ is 2-set-transitive.

###### Proof.

As $\mathfrak{B}$ is homogeneous with finite relational signature,
$\mathfrak{B}$ must be $\omega$-categorical. For 2-set-transitivity, consider
any four elements $a,b,c,d\in B$ such that $a\neq b$ and $c\neq d$. Because no
relation from the signature holds on $a,b$ or $c,d$, there is an isomorphism
between the substructure induced by $\left\\{a,b\right\\}$ in $\mathfrak{B}$
and the substructure induced by $\left\\{c,d\right\\}$ in $\mathfrak{B}$ that
maps $(a,b)$ to $(c,d)$. Due to homogeneity of $\mathfrak{B}$, this
isomorphism extends to an automorphism of $\mathfrak{B}$. Therefore,
$\mathfrak{B}$ is 2-set-transitive. ∎

######  Example 4.4.

An example for a structure $\mathfrak{B}$ satisfying the conditions of Lemma
4.3 is the Fraïssé-limit of all finite 3-uniform hypergraphs which do not
embed a tetrahedron (a surface of the tetrahedron corresponds to a hyperedge).
Let $\mathfrak{B}$ be this limit structure with its ternary edge relation $E$
and add $\neq$ to the signature. Then $\mathfrak{B}$ is 2-set-transitive by
Lemma 4.3. Furthermore, a cross prevention formula for $\mathfrak{B}$ is

$\phi(x,y,u,v)\mathrel{\vcentcolon\equiv}\exists
a,b\big{(}E(x,a,b)\operatorname{\wedge}E(u,a,b)\operatorname{\wedge}E(x,u,a)\operatorname{\wedge}E(y,v,b)\big{)}.$

This formula describes a tetrahedron between $a,b,x,u$, except that the edge
$E(x,u,b)$ is replaced by $E(y,v,b)$. It is easy to check that both
$\phi(x,y,u,v)\operatorname{\wedge}x=y$ and
$\phi(x,y,u,v)\operatorname{\wedge}u=v$ allow solutions $s_{1},s_{2}$
respectively, such that $s_{1}(x,u,v)$ and $s_{2}(x,y,u)$ are injective but
$\phi(x,y,u,v)\operatorname{\wedge}x=y\operatorname{\wedge}u=v$ is
unsatisfiable. Furthermore, $\operatorname{Age}(\mathfrak{B})$ has the strong
amalgamation property and therefore, $\mathfrak{B}$ does not have algebraicity
and hence it has Property $J$ by Proposition 2.3.

The example can be generalized to work with any complete 3-uniform hypergraph
on $n$ vertices for $n\geq 4$ instead of a tetrahedron (i.e., $n=4$).

To give examples for Theorem 1.4 that are not covered by the Nelson-Oppen
combination criterion we need structures with Property $J$, with polynomial-
time tractable CSP, and without convexity. Here is one such structure and an
ostensibly harmless combination partner:

######  Example 4.5.

Let $\mathfrak{B}_{1}$ be the relational structure
$({\mathbb{Q}};\neq,<,R_{\operatorname{mi}})$ where $R_{\operatorname{mi}}$ is
defined as in Example 4.1. Let
$\mathfrak{B}_{2}\mathrel{\vcentcolon=}({\mathbb{Q}};\prec)$ where $\prec$
also denotes the strict order of the rationals (we chose a different symbol
than $<$ to make the signatures disjoint). It is easy to see that
$\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ satisfy the assumptions of
Proposition 1.1, so they have a generic combination $\mathfrak{B}$.

From Example 4.1 we know that $\mathfrak{B}_{1}$ has Property $J$ and both
have polynomial-time tractable CSPs. Notice that $R_{\operatorname{mi}}$
prevents binary injective polymorphisms, i.e., it ensures that
$\mathfrak{B}_{1}$ does not have a convex theory (see Theorem 3.1). To apply
Theorem 1.4 we need a symbol for the disequality relation in
$\mathfrak{B}_{2}$. Let $\not\approx$ be another symbol for the disequality
relation on $\mathfrak{B}_{2}$. Then
$\mathfrak{B}_{1}\ast(\mathbb{Q},\not\approx,\prec)$ has the same CSP as
$\mathfrak{B}_{1}\ast\mathfrak{B}_{2}$, because $\not\approx$ and $\neq$ will
denote the same relation in
$\mathfrak{B}_{1}\ast(\mathbb{Q},\not\approx,\prec)$. Hence, Theorem 1.4
implies that the CSP of $\mathfrak{B}_{1}\ast\mathfrak{B}_{2}$ is NP-complete
(and we invite the reader to find an NP-hardness proof without using our
theorem).

This example shows how expansion of the signature, application of Theorem 1.4,
and subsequent reduction of the signature can extend the scope of Theorem 1.4.

Concluding this section, we would like to state the following corollary.

######  Corollary 4.6.

Let $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ be two first-order expansions of
$({\mathbb{Q}};<,\neq)$ with finite relational signatures. Rename the
relations of $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ so that
$\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ have disjoint signatures. Then
$\operatorname{CSP}(\operatorname{Th}(\mathfrak{B}_{1})\cup\operatorname{Th}(\mathfrak{B}_{2}))$
is in P if $\operatorname{CSP}(\mathfrak{B}_{1})$ and
$\operatorname{CSP}(\mathfrak{B}_{2})$ are in P and if both
$\operatorname{Th}(\mathfrak{B}_{1})$ and
$\operatorname{Th}(\mathfrak{B}_{2})$ are convex. Otherwise,
$\operatorname{CSP}(\operatorname{Th}(\mathfrak{B}_{1})\cup\operatorname{Th}(\mathfrak{B}_{2}))$
is NP-hard.

This follows from Proposition 1.1 which characterises the existence of a
generic combination of $T_{1}$ and $T_{2}$, and from Theorem 1.4 which
classifies the computational complexity of the generic combination.

##  5\. Difficulties for a General Complexity Classification

Let $T_{1}$ and $T_{2}$ be $\omega$-categorical theories with disjoint finite
relational signatures such that $\operatorname{CSP}(T_{1})$ is in P and
$\operatorname{CSP}(T_{2})$ is in P. The results in this section suggest that
in general we cannot hope to get a classification of the complexity of
$\operatorname{CSP}(T_{1}\cup T_{2})$. We use the result from [8] that there
are homogeneous directed graphs $\mathfrak{B}$ such that
$\operatorname{CSP}(\mathfrak{B})$ is undecidable. There are even homogeneous
directed graphs $\mathfrak{B}$ such that $\operatorname{CSP}(\mathfrak{B})$ is
_coNP-intermediate_ , i.e., in coNP, but neither coNP-hard nor in P [8]
(unless P = coNP). All of the homogeneous graphs $\mathfrak{B}$ used in [8]
can be described by specifying a set of finite tournaments $\mathcal{T}$. Let
$\mathcal{C}$ be the class of all finite directed loopless graphs
$\mathfrak{A}$ such that no tournament from $\mathcal{T}$ embeds into
$\mathfrak{A}$. It can be checked that $\mathcal{C}$ is a strong amalgamation
class; the Fraïssé-limits of those classes are called the _Henson digraphs_.

######  Proposition 5.1.

For every Henson digraph $\mathfrak{B}$ there exist $\omega$-categorical
convex theories $T_{1}$ and $T_{2}$ with disjoint finite relational signatures
such that $\operatorname{CSP}(T_{1})$ is in P, $\operatorname{CSP}(T_{2})$ is
in P, and $\operatorname{CSP}(T_{1}\cup T_{2})$ is polynomial-time Turing
equivalent to $\operatorname{CSP}(\mathfrak{B})$.

###### Proof.

Let $\mathfrak{B}_{1}$ be the structure obtained from $\mathfrak{B}$ by adding
a new element $a$ and adding the tuple $(a,a)$ to the edge relation $E$ of
$\mathfrak{B}$. Clearly, $\mathfrak{B}_{1}$ is $\omega$-categorical and
$\operatorname{CSP}(\mathfrak{B}_{1})$ is in P. Let $\mathfrak{B}_{2}$ be
$(\mathbb{N},\neq)$. Let $T_{i}$ be the theory of $\mathfrak{B}_{i}$, for
$i=1$ and $i=2$. We first present a polynomial-time reduction from
$\operatorname{CSP}(\mathfrak{B})$ to $\operatorname{CSP}(T_{1}\cup T_{2})$.

First observe that $x\mapsto a$ is the only solution to the instance
$\left\\{E(x,x)\right\\}$. Hence, given an instance $S$ of
$\operatorname{CSP}(\mathfrak{B})$ with variables $x_{1},\dots,x_{n}$, we can
give the following to an algorithm for $\operatorname{CSP}(T_{1}\cup T_{2})$:

$S^{*}\mathrel{\vcentcolon=}\left\\{E(x_{0},x_{0}),\,x_{0}\neq
x_{1},\dotsc,x_{0}\neq x_{n}\right\\}\cup S$

If there is a solution $s$ for $S^{*}$ in $\operatorname{CSP}(T_{1}\cup
T_{2})$, then the values $s(x_{1}),\dotsc,s(x_{n})$ are distinct from $a$ and
therefore $s|_{\left\\{x_{1},\dotsc,x_{n}\right\\}}$ is a solution for $S$ in
$\mathfrak{B}$. Likewise, if there is a solution $s$ for $S$ in
$\mathfrak{B}$, then $s$ and $x_{0}\mapsto a$ gives a solution for $S^{*}$ in
$\operatorname{CSP}(T_{1}\cup T_{2})$.

Next, we give a polynomial-time reduction from $\operatorname{CSP}(T_{1}\cup
T_{2})$ to $\operatorname{CSP}(\mathfrak{B})$. Consider an instance $S$ of
$\operatorname{CSP}(T_{1}\cup T_{2})$ and assume without loss of generality
that there is no conjunct of the form $x=y$ (substitute $y$ with $x$ otherwise
and revert the substitution after the algorithm otherwise). Now we consider
the directed graph $(V;R)$ where $V$ is the set of variables occurring in the
instance $S$ and $R$ is the set of pairs $(x_{i},\,x_{j})$ such that
$E(x_{i},x_{j})$ is in $S$.

Let $C_{1},\dots,C_{n}$ be the connected components of $(V;R)$ where two nodes
count as connected if there is some edge between them, regardless of its
direction. Furthermore define
$D\mathrel{\vcentcolon=}\left\\{(x_{i},x_{j})\mid x_{i}\neq x_{j}\text{ is a
constraint in }S\right\\}$ and label all $C_{k}$ where
$\left\\{E(x_{i},x_{j})\in S\mid x_{i},x_{j}\in C_{k}\right\\}$ has no
solution in $\mathfrak{B}$ with $a$. The algorithm proceeds as follows: If
there exists $(x_{i},x_{j})\in D$ such that both $x_{i}$ and $x_{j}$ are in
components labeled with $a$, then reject. Accept the instance otherwise.

To see that this is correct, notice that a connected component labeled $a$ can
only be satisfied by setting all variables in that component to $a$.
Therefore, all rejected cases must be unsatisfiable.

Now, consider an instance $S^{\prime}$ of $\operatorname{CSP}(\mathfrak{B})$
obtained by this reduction. There is a solution to the instance iff no
tournament $G_{F}\in\mathcal{T}$ can be embedded in the graph $G_{S^{\prime}}$
given by the edge constraints in $S^{\prime}$. If there is an embedding
$f\colon G_{F}\hookrightarrow G_{S^{\prime}}$ for some $G_{F}\in\mathcal{T}$,
then either $E(x_{i},x_{j})$ or $E(x_{j},x_{i})$ is in $S^{\prime}$ for all
variables $x_{i},x_{j}$ in the image of $f$. Hence, if we started with an
additional constraint $x_{i}\neq x_{j}$ (for two variables $x_{i},x_{j}$ with
$i\neq j$), removing this constraint would never make an otherwise
unsatisfiable instance satisfiable, because the same $G_{F}$ would still be
embeddable. Therefore, any satisfiable instance of
$\operatorname{CSP}(\mathfrak{B})$ is also satisfiable when arbitrary
additional $\neq$-constraints between different variables are enforced. Hence,
to construct a solution for the non-rejected cases of $S$, we take an
injective solution $s$ for the union of all unlabeled $C_{k}$ of $S^{\prime}$
such that $a$ is not in the image of $s$ and map all other variables to $a$.
It is easy to check that this satisfies all constraints in $S$. ∎

We mention that another example of two theories such that
$\operatorname{CSP}(T_{1})$ and $\operatorname{CSP}(T_{2})$ are decidable but
$\operatorname{CSP}(T_{1}\cup T_{2})$ is not can be found in [17].

Acknowledgements. We would like to thank Marcello Mamino for many helpful
discussions about this material. Furthermore, we thank the anonymous reviewers
for their helpful comments.

## References

  * [1] N. Ackerman, C. Freer, and R. Patel.  Invariant measures concentrated on countable structures.  Forum of Mathematics Sigma, 4, 2016.
  * [2] F. Baader and K. Schulz.  Combining constraint solving.  H. Comon, C. March, and R. Treinen, editors, Constraints in Computational Logics, 2001.
  * [3] L. Barto, M. Kompatscher, M. Olšák, M. Pinsker, and T. V. Pham.  The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems.  In Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science – LICS’17, 2017.  Preprint arXiv:1612.07551.
  * [4] L. Barto, J. Opršal, and M. Pinsker.  The wonderland of reflections.  Israel Journal of Mathematics, 223(1):363–398, Feb 2018.
  * [5] L. Barto and M. Pinsker.  The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems.  In Proceedings of the 31th Annual IEEE Symposium on Logic in Computer Science – LICS’16, pages 615–622, 2016.  Preprint arXiv:1602.04353.
  * [6] M. Bodirsky.  Complexity classification in infinite-domain constraint satisfaction.  Mémoire d’habilitation à diriger des recherches, Université Diderot – Paris 7. Available at arXiv:1201.0856v8, 2012.
  * [7] M. Bodirsky and J. Greiner.  Complexity of combinations of qualitative constraint satisfaction problems.  In 9th International Joint Conference on Automated Reasoning, IJCAR 2018, pages 263–278, 2018.
  * [8] M. Bodirsky and M. Grohe.  Non-dichotomies in constraint satisfaction complexity.  In L. Aceto, I. Damgard, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, editors, Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, pages 184 –196. Springer Verlag, July 2008\.
  * [9] M. Bodirsky and P. Jonsson.  A model-theoretic view on qualitative constraint reasoning.  Journal of Artificial Intelligence Research, 58:339–385, 2017.
  * [10] M. Bodirsky, P. Jonsson, and T. V. Pham.  The reducts of the homogeneous binary branching C-relation.  The Journal of Symbolic Logic, 81(4):1255–1297, 2016.
  * [11] M. Bodirsky, P. Jonsson, and T. V. Pham.  The Complexity of Phylogeny Constraint Satisfaction Problems.  ACM Transactions on Computational Logic (TOCL), 18(3), 2017\.  An extended abstract appeared in the conference STACS 2016.
  * [12] M. Bodirsky and J. Kára.  The complexity of equality constraint languages.  Theory of Computing Systems, 3(2):136–158, 2008.  A conference version appeared in the proceedings of Computer Science Russia (CSR’06).
  * [13] M. Bodirsky and J. Kára.  The complexity of temporal constraint satisfaction problems.  Journal of the ACM, 57(2):1–41, 2009.  An extended abstract appeared in the Proceedings of the Symposium on Theory of Computing (STOC).
  * [14] M. Bodirsky, B. Martin, M. Pinsker, and A. Pongrácz.  Constraint satisfaction problems for reducts of homogeneous graphs.  SIAM Journal on Computing, 48(4):1224–1264, 2019.  A conference version appeared in the Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pages 119:1–119:14.
  * [15] M. Bodirsky and J. Nešetřil.  Constraint satisfaction with countable homogeneous templates.  Journal of Logic and Computation, 16(3):359–373, 2006.
  * [16] M. Bodirsky, M. Pinsker, and A. Pongrácz.  Projective clone homomorphisms.  The Journal of Symbolic Logic, page 1–13, 09 2014.
  * [17] M. P. Bonacina, S. Ghilardi, E. Nicolini, S. Ranise, and D. Zucchelli.  Decidability and Undecidability Results for Nelson-Oppen and Rewrite-Based Decision Procedures, pages 513–527.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
  * [18] S. Braunfeld.  Towards the undecidability of atomicity for permutation classes via the undecidability of joint embedding for hereditary graph classes.  Available at arXiv:1903.11932, Mar 2019.
  * [19] R. Bruttomesso, S. Ghilardi, and S. Ranise.  Quantifier-free interpolation in combinations of equality interpolating theories.  ACM Transactions on Computational Logic (TOCL), 15(1):5, 2014\.
  * [20] A. A. Bulatov.  A dichotomy theorem for nonuniform csps.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319–330, 2017.
  * [21] P. J. Cameron.  Homogeneous permutations.  Electronic Journal of Combinatorics, 9(2), 2002.
  * [22] G. Cherlin.  The classification of countable homogeneous directed graphs and countable homogeneous $n$-tournaments.  AMS Memoir, 131(621), January 1998.
  * [23] M. Grohe, V. Guruswami, and S. Zivny.  The constraint satisfaction problem: Complexity and approximability (dagstuhl seminar 18231).  Dagstuhl Reports, 8(6):1–18, 2018.
  * [24] W. Hodges.  Model theory.  Cambridge University Press, 1993.
  * [25] M. Kompatscher and T. V. Pham.  A Complexity Dichotomy for Poset Constraint Satisfaction.  In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1–47:12, 2017.
  * [26] A. H. Lachlan.  Countable homogeneous tournaments.  Transactions of the American Mathematical Society (TAMS), 284:431–461, 1984.
  * [27] J. Linman and M. Pinsker.  Permutations on the random permutation.  Electronic Journal of Combinatorics, 22(2):1–22, 2015.
  * [28] G. Nelson and D. C. Oppen.  Simplification by cooperating decision procedures.  ACM Trans. Program. Lang. Syst., 1(2):245–257, Oct. 1979.
  * [29] D. Zhuk.  A proof of CSP dichotomy conjecture.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 331–342, 2017.