# Tractable Combinations of Theories via Sampling

Manuel Bodirsky, Johannes Greiner  Institut für Algebra
Technische Universität Dresden<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

For a first-order theory $T$, the Constraint Satisfaction Problem of $T$ is
the computational problem of deciding whether a given conjunction of atomic
formulas is satisfiable in some model of $T$. In this article we develop
sufficient conditions for polynomial-time tractability of the constraint
satisfaction problem for the union of two theories with disjoint relational
signatures. To this end, we introduce the concept of sampling for theories and
show that samplings can be applied to examples which are not covered by the
seminal result of Nelson and Oppen.

Both authors have received funding from the European Research Council (ERC
Grant Agreement no. 681988, CSP-Infinity), and the DFG Graduiertenkolleg 1763
(QuantLA)

##  1\. Introduction

Reasoning tasks for intelligent agents often require to check whether certain
configurations or situations are legitimate or possible. Such decision
problems can often be modelled as _Constraint Satisfaction Problems (CSPs)_.
The CSP of a first-order theory $T$ with finite relational signature $\tau$ is
the computational problem of deciding whether a set of atomic $\tau$-formulas
is satisfiable in some model of $T$. In fact, any decision problem is
polynomial-time Turing equivalent to a CSP [5]. Often, reasoners have to
decide instances of $\operatorname{CSP}(T_{1}\cup T_{2})$ where $T_{1}$ and
$T_{2}$ are first-order theories with disjoint relational signatures such that
$\operatorname{CSP}(T_{1})$ and $\operatorname{CSP}(T_{2})$ are well
understood. This problem has already be studied by Nelson and Oppen [17] and
many others have continued this line of research (see for example Baader and
Schulz [2]). CSPs of unions of theories are at the heart of SMT-Solvers (SAT
Modulo Theories) and occur frequently in software verification [10].

The results of Nelson and Oppen [17, 18] provide sufficient conditions for the
polynomial-time tractability of $\operatorname{CSP}(T_{1}\cup T_{2})$,
covering a great variety of theories. Schulz [19] as well as Bodirsky and
Greiner [4] have shown that in many situations, the conditions of Nelson and
Oppen are also necessary for polynomial-time tractability (unless P = NP).

In this article we will present new sufficient conditions for polynomial-time
tractability of $\operatorname{CSP}(T_{1}\cup T_{2})$, and present examples
which show that our conditions are incomparable to the conditions provided by
Nelson and Oppen. To prove our results, we introduce the notion of _sampling_
for theories and show how to apply samplings in order to solve
$\operatorname{CSP}(T_{1}\cup T_{2})$ in polynomial time. In particular, we
construct a sampling for $T_{1}\cup T_{2}$ from given samplings for $T_{1}$
and $T_{2}$.

##  2\. Sampling for a Theory

Let $\tau$ be a finite _relational signature_ , i.e., a finite set of relation
symbols, each of which endowed with a natural number denoting its arity. A
_$\tau$ -structure_ $\mathfrak{A}$ is a tuple starting with a set $A$,
followed by an $n$-ary relation $R^{\mathfrak{A}}\subseteq A^{n}$ for each
symbol $R\in\tau$ of arity $n$. We will always denote structures with
uppercase fraktur letters and their domain with the corresponding uppercase
Latin letter. A _theory_ is a set of first-order sentences. A _$\tau$ -theory_
is a theory where all non-logical symbols are in $\tau$. By
$\operatorname{Th}(\mathfrak{A})$ we denote the _theory of $\mathfrak{A}$_,
i.e., the set of all first-order sentences which are satisfied in
$\mathfrak{A}$. A $\tau$-structure $\mathfrak{A}$ is a _model_ of a
$\tau$-theory $T$, if all sentences of $T$ are satisfied in $\mathfrak{A}$. An
_atomic $\tau$-formula_ is either of the form $R(x_{1},\dots,x_{n})$ with
$R\in\tau$ of arity $n$ and variables $x_{1},\dots,x_{n}$, of the form
$x_{1}=x_{2}$, or of the form $\bot$, indicating the logical “false”.

We now present the central definitions of this article.

######  Definition 2.1.

Let $\tau$ be a finite relational signature and $T$ a $\tau$-theory.

  * •

A _sampling_ for $T$ is a sequence $(L_{n})_{n\in\mathbb{N}}$ of finite sets
of finite $\tau$-structures such that for all $n\in\mathbb{N}$ and all
conjunctions of atomic $\tau$-formulas $\phi$ with at most $n$ variables,
there exists a model for $T$ in which $\phi$ is satisfiable if and only if
there exists $\mathfrak{B}\in L_{n}$ such that $\phi$ is satisfiable in
$\mathfrak{B}$. An element of $L_{n}$ is called _$n$ -sample_, or simply
_sample_ , for $T$.

  * •

Let $(L_{n})_{n\in\mathbb{N}}$ be a sampling for a theory $T$. We define
$\lvert L_{n}\rvert\coloneqq\sum_{\mathfrak{B}\in L_{n}}\lvert B\rvert$. A
sampling $(L_{n})$ is _polynomial_ if there exists a polynomial
$p\in\mathbb{Z}[x]$ such that $\lvert L_{n}\rvert\leq p(n)$ for all
$n\in\mathbb{N}$.

  * •

A sampling $(L_{n})_{n\in\mathbb{N}}$ is _computable_ if there exists an
algorithm that, given $n$, computes $L_{n}$. If this algorithm runs in time
polynomial in $n$, then $(L_{n})$ is _computable in polynomial time_.

  * •

A _sampling_ for a structure $\mathfrak{A}$ is a sampling for
$\operatorname{Th}(\mathfrak{A})$.

  * •

For $n\geq 1$, let $S_{n}(T)$ be the class of all finite $\tau$-structures
$\mathfrak{B}_{n}$ such that a conjunction of atomic $\tau$-formulas with at
most $n$ variables is satisfiable in $\mathfrak{B}_{n}$ if and only if it is
satisfiable in some model of $T$.

While we are not aware that samplings have been defined for theories before,
there is a definition for structures by Bodirsky, Macpherson and Thapper [6]
and we will now compare the two notions. We need the classical notion of a CSP
which is defined for structures instead of theories. Let $\tau$ be a finite
relational signature and $\mathfrak{A}$ a $\tau$-structure.
$\operatorname{CSP}(\mathfrak{A})$ is the computational problem of deciding
whether a conjunction of atomic $\tau$-formulas is satisfiable in
$\mathfrak{A}$. Notice that
$\operatorname{CSP}(\operatorname{Th}(\mathfrak{A}))=\operatorname{CSP}(\mathfrak{A})$
holds for all relational structures $\mathfrak{A}$, because
$\operatorname{Th}(\mathfrak{A})$ explicitly states which instances are
satisfiable. Therefore, the definition of ‘sampling for $\mathfrak{A}$’ in [6]
can be attained from our definition by imposing the additional conditions on
$(L_{n})$ that for all $n\in\mathbb{N}$ the set $L_{n}$ may only contain one
structure $\mathfrak{B}_{n}$ and that $\mathfrak{B}_{n}$ needs to have a
homomorphism to $\mathfrak{A}$. Hence, any structure which has ‘efficient
sampling’ in the definition of Bodirsky, Macpherson and Thapper has a sample
which is computable in polynomial time in our definition, and is thus
polynomial.

We will now prove that samplings for _structures_ only require one element in
each $L_{n}$, just like in the definition of Bodirsky, Macpherson and Thapper.
However, we will see in Example 3.11 that dropping the requirement that
$\mathfrak{B}_{n}$ is homomorphic to $\mathfrak{A}$ allows smaller samples in
some cases and can therefore reduce the runtime of algorithms that run on the
samples.

######  Definition 2.2.

Let $T$ be a theory with finite relational signature. $T$ has the _Joint
Homomorphism Property (JHP)_ if 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}$.

######  Proposition 2.3 (Proposition 2.1 in [4]).

Let $T$ be a theory with finite relational signature. Then there exists a
model $\mathfrak{A}$ of $T$ such that
$\operatorname{CSP}(\mathfrak{A})=\operatorname{CSP}(T)$ if and only if $T$
has the _Joint Homomorphism Property (JHP)_.

######  Definition 2.4.

For a set $L$ of $\tau$-structures we define the _disjoint union_
$\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits_{\mathfrak{B}\in
L}\mathfrak{B}$ as the structure with domain
$\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits_{\mathfrak{B}\in
L}B$ and a $k$-ary relation $R\in\tau$ holds on a tuple $t$ if and only if
there exists $\mathfrak{B}\in L$ such that $t\in B^{k}$ and $R(t)$ holds in
$\mathfrak{B}$.

######  Proposition 2.5.

Let $T$ be a theory with JHP and let $(L_{n})_{n\in\mathbb{N}}$ be a sampling
for $T$. Then $(L^{\prime}_{n})_{n\in\mathbb{N}}$ with
$L^{\prime}_{n}\coloneqq\\{\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits_{\mathfrak{B}\in
L_{n}}\mathfrak{B}\\}$ is also a sampling for $T$. Moreover, $\lvert
L^{\prime}_{n}\rvert=\lvert L_{n}\rvert$ for all $n\in\mathbb{N}$.

###### Proof.

Let $\phi$ be a conjunction of atomic $\tau$-formulas with variables in
$V\coloneqq\\{x_{1},\dots,x_{n}\\}$. If $\phi$ is satisfiable in $T$, then it
is satisfiable in some $\mathfrak{B}\in L_{n}$ and therefore in
$\mathfrak{C}\coloneqq\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits_{\mathfrak{B}\in
L_{n}}\mathfrak{B}$. Assume that $\phi$ is satisfiable in $\mathfrak{C}$. Let
$s\colon V\rightarrow C$ be a satisfying assignment. Then $s$ induces a
partition $V_{1},\dots,V_{k}$ on $V$, where two elements of $V$ are in the
same part if they are mapped into the same element of $L_{n}$. However, $\phi$
cannot contain a conjunct $R(\dots,x_{i},\dots,x_{j},\dots)$ with $x_{i}\in
V_{i}$ and $x_{j}\in V_{j}$ for $i\neq j$, as this relation would not hold in
$\mathfrak{C}$. Hence, $\phi$ is equivalent to a conjunction
$\phi_{1}\operatorname{\wedge}\dots\operatorname{\wedge}\phi_{k}$, where each
$\phi_{i}$ is itself a conjunction of atomic $\tau$-formulas, $s$ maps all
variables of $\phi_{i}$ into $V_{i}$ and $\phi_{i}$ and $\phi_{j}$ have no
common variables for $i\neq j$. Let $\mathfrak{A}$ be a model of $T$ such that
$\operatorname{CSP}(\mathfrak{A})=\operatorname{CSP}(T)$, which exists by
Proposition 2.3. As $(L_{n})_{n\in\mathbb{N}}$ is a sampling for $T$, it is
also a sampling for $\mathfrak{A}$ and therefore, each $\phi_{i}$ is
satisfiable in $\mathfrak{A}$. Hence, $\phi$ is satisfiable in $\mathfrak{A}$
and therefore in $T$. We have $\lvert
L^{\prime}_{n}\rvert=\sum_{\mathfrak{B}\in L_{n}}\lvert B\rvert=\lvert
L_{n}\rvert$. ∎

Due to Proposition 2.5, and the fact that
$\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits_{\mathfrak{B}\in
L_{n}}\mathfrak{B}$ has the same size as $|L_{n}\rvert$, we will now often
assume that samplings for structures contain only one element
$\mathfrak{B}_{n}\in S_{n}(\operatorname{Th}(\mathfrak{A}))$ in $L_{n}$ (for
all $n\in\mathbb{N}$). We will write $(\mathfrak{B}_{n})_{n\in\mathbb{N}}$
instead of $(\\{\mathfrak{B}_{n}\\})_{n\in\mathbb{N}}$. It will become clear
in Section 3 why we will not assume that sampling of structures make this
assumption in general.

To justify why our definition of ‘sampling’ allows $L_{n}$ to contain multiple
structures in general, we would like to give an example of a theory $T$ which
has a sampling but no sampling $(L_{n})$ of $T$ has only one element in
$L_{n}$ for some $n\geq 2$.

######  Example 2.6 (similar to Example 2.2 in [4]).

Let $\tau$ be a signature consisting of the unary symbols $O,P,Q$ and the
binary symbol $I$. Let $T$ be the set of the following sentences

$\displaystyle\forall x,y.((O(x)\operatorname{\wedge}O(y))\Rightarrow x=y),$
$\displaystyle\forall x.\neg(P(x)\operatorname{\wedge}Q(x)),\quad\text{and}$
$\displaystyle\forall x,y.(I(x,y)\Leftrightarrow\neg(x=y)).$

The following is a sampling for $T$ which is computable in polynomial time:
For $n\in\mathbb{N}$ let $L_{n}$ consist of $\mathfrak{B}_{1}$ and
$\mathfrak{B}_{2}$ defined on $\\{1,\dots,2n\\}$ where
$P^{\mathfrak{B}_{1}}=P^{\mathfrak{B}_{2}}\coloneqq\\{1,\dots,n\\}$,
$Q^{\mathfrak{B}_{1}}=Q^{\mathfrak{B}_{2}}\coloneqq\\{n+1,\dots,2n\\}$,
$O^{\mathfrak{B}_{1}}\coloneqq\\{1\\}$ and
$O^{\mathfrak{B}_{2}}\coloneqq\\{n+1\\}$. In both structures, the $I$-relation
denotes the inequality relation. While it is easy to check that
$(L_{n})_{n\in\mathbb{N}}$ is a sampling for $T$, there is no sampling with
only one element in $L_{n}$ for some $n\geq 2$. To prove this, consider the
formulas $\phi_{1}\mathrel{\vcentcolon\equiv}O(x)\operatorname{\wedge}P(x)$,
which is satisfiable in $\mathfrak{B}_{1}$, and $\phi_{2}\coloneqq
O(y)\operatorname{\wedge}Q(y)$, which is satisfiable in $\mathfrak{B}_{2}$.
Assume that both are satisfiable in some $\tau$-structure $\mathfrak{B}$. Then
there exists $a\in O^{\mathfrak{B}}\cap P^{\mathfrak{B}}$ and $b\in
O^{\mathfrak{B}}\cap Q^{\mathfrak{B}}$. If $a=b$, then $\psi_{1}\coloneqq
P(x)\operatorname{\wedge}Q(x)$ is satisfiable in $\mathfrak{B}$. If $a\neq b$,
then $\psi_{2}\coloneqq
O(x)\operatorname{\wedge}O(y)\operatorname{\wedge}I(x,y)$ is satisfiable in
$\mathfrak{B}$ or $\psi_{3}\coloneqq I(x,y)\operatorname{\wedge}x=y$ is
satisfiable in $\mathfrak{B}$ (in case $I^{\mathfrak{B}}$ is not the
complement of equality). However, none of $\psi_{1},\psi_{2},\psi_{3}$ is
satisfiable in some model of $T$, contradiction.

To characterise theories with a computable sampling, we need the following
definition.

######  Definition 2.7.

Let $\tau$ be a relational signature and let $\phi$ be a conjunction of atomic
$\tau$-formulas with variables $x_{1},\dots,x_{n}$. The _canonical database_
$D(\phi)$ is defined as the structure with domain $x_{1},\dots,x_{n}$ such
that a tuple $t$ is in a relation $R^{D(\phi)}$ for $R\in\tau$ if and only if
$R(t)$ is a conjunct of $\phi$.

Clearly, there is a homomorphism from $D(\phi)$ to $\mathfrak{A}$ if and only
if $\phi$ is satisfiable in $\mathfrak{A}$.

######  Proposition 2.8.

Let $T$ be a theory with finite relational signature. Then, $T$ has a
computable sampling if and only if $\operatorname{CSP}(T)$ is decidable.

###### Proof.

Let $\tau$ be the signature of $T$. Suppose there exists a computable sampling
$(L_{n})_{n\in\mathbb{N}}$ for $T$. Let $\phi$ be a conjunction of atomic
$\tau$-formulas with at most $n$ variables. Then there are only finitely many
maps from $D(\phi)$ to structures in $L_{n}$ and for each of them we can
determine whether it is a homomorphism or not. Therefore
$\operatorname{CSP}(T)$ is decidable.

Conversely, suppose that $\operatorname{CSP}(T)$ is decidable. There are only
finitely many atomic formulas on $n$ variables because $\tau$ is finite and
the arity of each relation is finite. Hence, there are only finitely many
conjunctions of atomic formulas with at most $n$ variables such that no
conjunct is repeated. Using the decision procedure for
$\operatorname{CSP}(T)$, we may determine which of the conjunctions are
satisfiable in some model of $T$ and define $L_{n}$ as the set of all
canonical databases of the satisfiable conjunctions. Then, by construction,
$(L_{n})$ is a sampling for $T$. ∎

To determine whether a theory has a polynomial sampling the following general
observation is helpful.

######  Observation 2.9.

Let $\mathfrak{A}$ be a structure with finite relational signature $\tau$. By
Proposition 2.5, determining whether a polynomial sampling for $\mathfrak{A}$
exists is equivalent to determining whether for all $n\in\mathbb{N}$ there
exists $\mathfrak{B}_{n}\in S_{n}(\operatorname{Th}(\mathfrak{A}))$ such that
$(\mathfrak{B}_{n})$ is a polynomial sampling. If $\mathfrak{B}_{n}\in
S_{n}(\operatorname{Th}(\mathfrak{A}))$ and there exists a homomorphism
$h\colon\mathfrak{B}_{n}\rightarrow\mathfrak{A}$, then $h(\mathfrak{B}_{n})\in
S_{n}(\operatorname{Th}(\mathfrak{A}))$ and $\lvert h(B_{n})\rvert\leq\lvert
B_{n}\rvert$. If we can prove that each element of $S_{n}$ homomorphically
maps to $\mathfrak{A}$ we can therefore assume that $L_{n}$ consists of a
single substructure of $\mathfrak{A}$. An element of
$S_{n}(\operatorname{Th}(\mathfrak{A}))$ which is a substructure of
$\mathfrak{A}$ is called an _$n$ -universal substructure_ of $\mathfrak{A}$.
Minimal sizes of $n$-universal substructures are easier to determine and have
been explored in the past [16, 12, 15].

In general, $S_{n}(\operatorname{Th}(\mathfrak{A}))$ may contain structures
which are smaller than the smallest $n$-universal substructure of
$\mathfrak{A}$ and Example 3.11 will provide an example for this case.

To exemplify the use of Observation 2.9 we will now use it to prove that a
certain theory does not have a polynomial sampling. The theory $T$ in Lemma
2.10 is contained in the theory of every undirected, loopless graphs with a
binary relation symbol $E$ for the edge relation and a binary relation symbol
$N$ for the set of all pairs of distinct elements that are not related by an
edge.

######  Lemma 2.10.

Let $\tau$ consist of the binary relation symbols $E$ and $N$ and let $T$
contain only the sentence

$\displaystyle\forall x,y.\big{(}$ $\displaystyle\neg
E(x,x)\operatorname{\wedge}\neg(E(x,y)\operatorname{\wedge}\neg E(y,x))$
$\displaystyle\neg
N(x,x)\operatorname{\wedge}\neg(E(x,y)\operatorname{\wedge}N(x,y))\big{)}.$

Then there is a sampling for $T$ but not a polynomial sampling.

###### Proof.

First notice that $\operatorname{CSP}(T)$ is decidable (in polynomial-time)
because it suffices to check, after eliminating equalities by substitution of
variables, that the instance does not contain $\bot$, $E(x,x)$, $N(x,x)$,
$E(x,y)\operatorname{\wedge}N(x,y)$ or $E(y,x)\operatorname{\wedge}N(x,y)$ for
any two variables $x,y$. Therefore, there exists a sampling $(L_{n})$ for $T$
by Proposition 2.8. Fix $n\geq 2$. Notice that the disjoint union of two
models of $T$ is again a model of $T$. Therefore, $T$ has the JHP and we may
without loss of generality assume that $L_{n}$ contains only one structure
$\mathfrak{B}$ due to Proposition 2.5. For the structure
$(B;E^{\mathfrak{B}})$ we know that it is without loops as otherwise $E(x,x)$
is satisfiable in $\mathfrak{B}$, contradiction. Furthermore, we may assume
that $(B;E^{\mathfrak{B}})$ is an undirected graph, because adding the reverse
direction to an edge does not increase the size of $\mathfrak{B}$ and does not
change the satisfiability of instances in $\mathfrak{B}$. To prove the latter,
notice that instances satisfiable in $\mathfrak{B}$ cannot become
unsatisfiable in $\mathfrak{B}^{\prime}$, where $E(a,b)$ has been added,
because all homomorphisms to $\mathfrak{B}$ are also homomorphisms to
$\mathfrak{B}^{\prime}$. Suppose there exists an instance $\phi$ which is not
satisfiable in $\mathfrak{B}$ but there exists a homomomorphism $h\colon
D(\phi)\rightarrow\mathfrak{B}^{\prime}$. Let $\phi^{\prime}$ be the instance
where all conjuncts $E(x,y)$ in $\phi$ with $h(x)=a$ and $h(y)=b$ are replaced
by $E(y,x)$. Then $h$ is a homomomorphism from $D(\phi^{\prime})$ to
$\mathfrak{B}$, and therefore $\phi^{\prime}$ is satisfiable in some model of
$T$. As $E$ is symmetric in all models of $T$, $\phi$ is satisfiable in some
model of $T$ and therefore in $\mathfrak{B}$, contradiction.

Lastly, we know that $N^{\mathfrak{B}}\subseteq B^{2}\setminus
E^{\mathfrak{B}}$ must hold, as $E(x,y)\operatorname{\wedge}N(x,y)$ is
satisfiable in $\mathfrak{B}$ otherwise. Therefore, $\mathfrak{B}$ is
homomorphic to a model $\mathfrak{R}$ of $T$ in which $\forall
x,y.(N(x,y)\Leftrightarrow x\neq y\operatorname{\wedge}\neg E(x,y))$ holds and
which contains all undirected loopless finite graphs as induced subgraphs.
Then $\lvert\mathfrak{B}\rvert$ is at least the size of the smallest
$n$-universal substructure of $\mathfrak{R}$ by Observation 2.9. However, due
to results by Noga Alon [1] we know that any substructure of $\mathfrak{R}$
which contains all graphs of size at most $n$ as induced subgraphs has size
exponential in $n$ and that this does not depend on the choice of
$\mathfrak{R}$. ∎

Theories with polynomial samplings include all theories of finite structures,
the theory of successor on the natural numbers, and the theories of structures
in Lemma 3.5 and Lemma 3.6 below.

##  3\. Sampling for Unions of Theories

Let $T_{1},T_{2}$ be two theories with disjoint relational signatures and that
$T_{1}$ and $T_{2}$ have polynomial samplings. In this section we will present
sufficient conditions on $T_{1}$ and $T_{2}$ such that $T_{1}\cup T_{2}$ has
polynomial sampling. To this end, we will need to construct models for
$T_{1}\cup T_{2}$. Let $\tau_{1},\tau$ be relational signatures with
$\tau_{1}\subseteq\tau$ and $\mathfrak{A}$ a $\tau$-structure. The _$\tau_{1}$
-reduct_ of $\mathfrak{A}$, written $\mathfrak{A}^{\tau_{1}}$, is the
structure we get when all relations with symbols not contained in $\tau_{1}$
are removed from $\mathfrak{A}$. The following definition goes back to Tinelly
and Ringeisen [20].

######  Definition 3.1.

Let $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ be $\tau_{1}$ and $\tau_{2}$
structures respectively. A $\tau_{1}\cup\tau_{2}$-structure $\mathfrak{A}$ is
a _fusion_ of $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ if and only if
$\mathfrak{A}^{\tau_{i}}$ is isomorphic to $\mathfrak{A}_{i}$ for $i=1$ and
$i=2$.

######  Proposition 3.2 (Proposition 1 and Lemma 1 in [2]).

For $i=1,2$, let $T_{i}$ be a $\tau_{i}$ theory. A
$\tau_{1}\cup\tau_{2}$-structure $\mathfrak{A}$ is a model of $T_{1}\cup
T_{2}$ if and only if $\mathfrak{A}$ is a fusion of a model for $T_{1}$ and a
model for $T_{2}$. Furthermore, two structures have a fusion if and only if
their domains have the same cardinality.

The proof of Lemma 1 in [2] essentially argues that any bijection between the
domains of two structures with disjoint signatures defines a fusion of the two
structures, which is a fact we will use later on.

It is an easy observation that an instance
$\phi_{1}\operatorname{\wedge}\phi_{2}$ of $\operatorname{CSP}(T_{1}\cup
T_{2})$ is satisfiable if and only if for $i=1$ and $i=2$ there exist models
$\mathfrak{A}_{i}$ of $T_{i}$ with $\lvert A_{1}\rvert=\lvert A_{2}\rvert$
such that $\phi_{i}$ is satisfiable in $\mathfrak{A}_{i}$ and the satisfying
assignments of $\phi_{1}$ and $\phi_{2}$ identify exactly the same variables.
The following notion describes a property of a sampling that allows us to
transfer identifications of variables between models and samples.

######  Definition 3.3.

We call a sampling $(L_{n})_{n\in\mathbb{N}}$ for $T$ _equality-matching_ if
for all $n\in\mathbb{N}$ and all conjunctions of atomic $\tau$-formulas $\phi$
with variables in $\\{x_{1},\dots,x_{n}\\}$ and for any conjunction $\psi$ of
equalities and negated equalities on $\\{x_{1},\dots,x_{n}\\}$, there exists a
model of $T$ in which $\phi\operatorname{\wedge}\psi$ is satisfiable if and
only if there exists $\mathfrak{B}\in L_{n}$ such that
$\phi\operatorname{\wedge}\psi$ is satisfiable in $\mathfrak{B}$. A sampling
is _equality-matching_ for a structure $\mathfrak{A}$ if it is equality-
matching for $\operatorname{Th}(\mathfrak{A})$.

To be equality-matching will be the property that samplings for $T_{1}$ and
$T_{2}$ must satisfy in order to construct a sampling for $T_{1}\cup T_{2}$ in
Theorem 3.8. An example for an equality-matching sampling is the one
constructed in Example 2.6 because $I$ is the negation of equality in all
models of $T$ and the constructed samples and therefore, the instances of
$\operatorname{CSP}(T)$ themselves can specify how to identify variables.
Also, the sampling constructed in the proof of Proposition 2.8 is equality-
matching if there exists $I\in\tau$ such that in all models of $T$ we have
$I(x,y)\Leftrightarrow\neg(x=y)$.

Another class of theories where an equality-matching sampling always exists
are $\omega$-categorical theories. A theory is _$\omega$ -categorical_ if it
has only one countable model (up to isomorphism). For a structure
$\mathfrak{A}$, the _orbit_ of $t\in A^{k}$ is
$\\{\alpha(t)\mid\alpha\in\operatorname{Aut}(\mathfrak{A})\\}$ where
$\operatorname{Aut}(\mathfrak{A})$ is the set of automorphisms of
$\mathfrak{A}$ and $\alpha$ is applied componentwise.

######  Proposition 3.4.

Let $T$ be an $\omega$-categorical theory with finite relational signature.
Then there exists an equality-matching sampling for $T$.

###### Proof.

If $T$ has an infinite model $\mathfrak{A}$ then there exists a countably
infinite model $\mathfrak{A}^{\prime}$ of $T$ such that
$\operatorname{Th}(\mathfrak{A})=\operatorname{Th}(\mathfrak{A}^{\prime})$ by
the Downward Löwenheim-Skolem Theorem (see [13], page 90). If the unique
countable model $\mathfrak{A}$ of $T$ is finite, then $(L_{n})$ with
$L_{n}\coloneqq\\{\mathfrak{A}\\}$ for all $n\in\mathbb{N}$ is an equality-
matching sampling for $T$ and we are done. We may therefore assume that an
instance $\phi$ in conjunction with equalities and disequalities is
satisfiable in some model of $T$ if and only if it is satisfiable in a fixed
countably infinite structure $\mathfrak{A}$. By the theorem of Engeler, Ryll-
Nardzewski and Svenonius (see [13] page 341) there are only finitely many
orbits of $n$-tuples in $\mathfrak{A}$. To construct an $n$-sample for
$\mathfrak{A}$ we pick a tuple from each of the finitely many orbits of length
$n$ and define $\mathfrak{B}_{n}$ to be the substructure of $\mathfrak{A}$
whose domain is the union of all elements appearing in these tuples. We claim
that $(\mathfrak{B}_{n})$ is an equality-matching sampling for $T$.

Let $\phi$ be a conjunction of atomic formulas and $\psi$ a conjunction of
equalities and negated equalities, both on variables $x_{1},\dots,x_{n}$.
Clearly, if there exists a homomorphism from
$D(\phi\operatorname{\wedge}\psi)$ to $\mathfrak{B}_{n}$ then there exists a
homomorphism from $D(\phi\operatorname{\wedge}\psi)$ to $\mathfrak{A}$ because
$\mathfrak{B}_{n}$ embedds into $\mathfrak{A}$. If $h\colon
D(\phi\operatorname{\wedge}\psi)\rightarrow\mathfrak{A}$ is a homomorphism,
then the image of $h$ is a tuple $t$ of length at most $n$. Then, there is a
tuple $t^{\prime}$ in $\mathfrak{B}_{n}$ with the same orbit as $t$. Hence, we
can choose $\alpha\in\operatorname{Aut}(\mathfrak{A})$ such that
$\alpha(t)=t^{\prime}$ and $\alpha\circ h$ is a homomorphism from
$D(\phi\operatorname{\wedge}\psi)$ to $\mathfrak{B}_{n}$. ∎

It follows from Proposition 2.8 that there are are $\omega$-categorical
structures without computable sampling, because some of those structures have
an undecidable CSP [7]. There are also theories with a sampling computable in
polynomial time, but without polynomial equality-matching sampling. Indeed,
let $\tau$ contain the binary relations $E$ and $N$ and let $T$ contain only

$\displaystyle\forall x,y\,\big{(}$
$\displaystyle\neg(E(x,y)\operatorname{\wedge}\neg
E(y,x))\operatorname{\wedge}$
$\displaystyle\neg(E(x,y)\operatorname{\wedge}N(x,y)\operatorname{\wedge}x\neq
y)\big{)}.$

Then $L_{n}\coloneqq(\\{0\\},E,N)$ with $E=N\coloneqq\\{(0,0)\\}$ for all
$n\in\mathbb{N}$ yields a sampling for $T$. If there exists a polynomial
equality-matching sampling for $T$, then there exists a polynomial sampling
for $T^{\prime}\coloneqq T\cup\operatorname{Th}(\mathbb{Z};\neq)$ by
Proposition 3.10. However, in $\operatorname{CSP}(T^{\prime})$ we can define
relations $E^{\prime},N^{\prime}$ which must satisfy the theory from Lemma
2.10 by $E^{\prime}(x,y)\coloneqq E(x,y)\operatorname{\wedge}x\neq y$ and
$N^{\prime}(x,y)\coloneqq N(x,y)\operatorname{\wedge}x\neq y$. Therefore, a
polynomial equality-matching sampling for $T^{\prime}$ cannot exist.

It is in general not true that if $(L_{n})_{n\in\mathbb{N}}$ is equality-
matching then
$(L^{\prime}_{n})_{n\in\mathbb{N}}\coloneqq(\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits_{\mathfrak{B}\in
L_{n}}\mathfrak{B})_{n\in\mathbb{N}}$ is equality-matching as well. An example
is $\mathfrak{A}=(\\{0,1\\};<)$ with $L_{4}$ consisting of two copies of
$\mathfrak{A}$. Then
$x_{1}<x_{2}\operatorname{\wedge}x_{3}<x_{4}\operatorname{\wedge}\bigwedge_{i<j}x_{i}\neq
x_{j}$ is not satisfiable in $\mathfrak{A}$ or $L_{4}$, but is satisfiable in
$(L_{4}^{\prime})$. Even homomorphic images of equality-matching samplings,
such as in Observation 2.9, need not be equality-matching.

For later use, we now present two classes of structures with equality-matching
sampling computable in polynomial time. If $\mathfrak{B}$ is a reduct of
$\mathfrak{A}$ and all relations in $\mathfrak{A}$ have a first-order
definition in $\mathfrak{B}$, then $\mathfrak{A}$ is called a _first-order
expansion_ of $\mathfrak{B}$.

######  Lemma 3.5.

All reducts of first-order expansions of ${(\mathbb{Q};<)}$ have an equality-
matching sampling computable in polynomial time.

###### Proof.

For all $n\in\mathbb{N}$ let $\mathfrak{B}_{n}$ be the substructure of
$(\mathbb{Q};<)$ with domain $\\{1,2,\dotsc,n\\}$. Then $(\mathfrak{B}_{n})$
is an equality-matching sampling for $(\mathbb{Q};<)$. This is because the
orbit of a tuple $t$ is fully determined by the order and identification of
the coordinates of $t$ and all possible orderings and identifications of $n$
variables homomorphically map to $\mathfrak{B}_{n}$. Therefore, the
constructed sampling is of the same kind as the one constructed in the proof
of Proposition 3.4 and therefore equality-matching.

Any relation which is first-order definable over a structure is a union of
orbits of that structure. As the constructed sampling consist of substructures
of $(\mathbb{Q};<)$ and each $n$-sample includes all orbits of length $n$, the
constructed sampling is also a sampling for reducts of first-order expansions
of $(\mathbb{Q};<)$. ∎

######  Lemma 3.6.

Let $P_{1},\dots,P_{m}$ be a partition of $\mathbb{Q}$ where all parts are
infinite and co-infinite. All reducts of first-order expansions of
$(\mathbb{Q};P_{1},\dotsc,P_{m})$ have an equality-matching sampling
computable in polynomial time.

###### Proof.

For all $n\in\mathbb{N}$ define $\mathfrak{B}_{n}$ as the substructure of
$(\mathbb{Q};P_{1},\dotsc,P_{m})$ with domain $\\{a_{1,1},\dotsc,a_{n,m}\\}$
where $a_{i,j}\in P_{j}$ for $1\leq i\leq n$ and $1\leq j\leq m$. Then
$(\mathfrak{B}_{n})$ is an equality-matching sampling for
$(\mathbb{Q};P_{1},\dotsc,P_{m})$. This is because the orbit of an $n$-tuple
$t$ in $(\mathbb{Q};P_{1},\dotsc,P_{m})$ is fully determined by
identifications of coordinates of $t$ and which coordinate belongs to which
$P_{i}$. It is easy to see that all possible identifications and assignments
of $n$ variables to $P_{1},\dots P_{m}$ can be realized in $\mathfrak{B}_{n}$.
Therefore, the constructed sampling is of the same kind as the one constructed
in the proof of Proposition 3.4 and therefore equality-matching.

The reason why $(\mathfrak{B}_{n})$ is also an equality-matching sampling for
reducts of first-order expansions of $(\mathbb{Q};P_{1},\dotsc,P_{m})$ is the
same as in the proof of Lemma 3.5. ∎

Another condition we need in order to construct a sampling for the union of
two theories is a primitive positive version of the classical concept of _no
algebraicity_ in model theory (see [13]). A formula is called _primitive
positive (pp)_ if it is a conjunction of atomic formulas where some variables
may be existentially quantified.

######  Definition 3.7.

A $\tau$-structure $\mathfrak{A}$ has _no pp-algebraicity_ if for any
primitive positive $\tau$-formula $\phi(x)$ with parameters
$a_{1},\dots,a_{n}$ the set $\\{b\in A\mid\mathfrak{A}\models\phi(b)\\}$ is
either contained in $\\{a_{1},\dots,a_{n}\\}$ or infinite.

It is easy to check that first-order expansions of $(\mathbb{Q};<)$ or
$(\mathbb{Q};P_{1},\dotsc,P_{m})$ do not have pp-algebraicity because $a<x<b$
has either no or infinitely many satisfying assignments in $(\mathbb{Q};<)$
(for all $a,b\in\mathbb{Q}$), and in $(\mathbb{Q};P_{1},\dots,P_{m})$ any two
distinct elements in $P_{i}$ are indistinguishable for first-order definable
relations. When it is clear from context that we mean a set, we will use $[n]$
as a shorthand for $\\{1,2,\dots,n\\}$.

We are now ready to present the first main result.

######  Theorem 3.8.

Let $T_{1}$ and $T_{2}$ be theories with finite relational and disjoint
signatures $\tau_{1},\tau_{2}$ respectively. If all models of $T_{1}$ and
$T_{2}$ do not have pp-algebraicity and $T_{1}$ and $T_{2}$ have equality-
matching samplings $(O_{n}),(P_{n})$ respectively, then there exists an
equality-matching sampling $(L_{n})$ for $T\coloneqq T_{1}\cup T_{2}$ with
$\lvert L_{n}\rvert=\lvert O_{n}\rvert\cdot\lvert P_{n}\rvert$ for all
$n\in\mathbb{N}$. If $(O_{n})$ and $(P_{n})$ are computable in polyonmial
time, then $(L_{n})$ is also computable in polynomial time.

###### Proof.

Let $(O_{n})$ and $(P_{n})$ be equality-matching samplings of $T_{1},T_{2}$,
respectively. Fix $n\in\mathbb{N}$ and let
$\\{\mathfrak{B}_{i,1},\dots,\mathfrak{B}_{i,p_{i}}\\}$ be $O_{n}$ for $i=1$
and $P_{n}$ for $i=2$. For all $i\in[p_{1}],j\in[p_{2}]$ we now define a
$\tau_{1}\cup\tau_{2}$-structure $\mathfrak{M}_{i,j}$ with domain
$M_{i,j}\coloneqq B_{1,i}\times B_{2,j}$ as follows.

For $R\in\tau_{1}$ of arity $k$ we define

$\displaystyle((a_{1},b_{1}),\dots,(a_{k},b_{k}))\in
R^{\mathfrak{M}_{i,j}}\Leftrightarrow$ $\displaystyle(\forall
i,j.(a_{i}=a_{j}\Leftrightarrow
b_{i}=b_{j}))\operatorname{\wedge}(a_{1},\dots,a_{k})\in
R^{\mathfrak{B}_{1,i}}.$

Analogously, we define for $R\in\tau_{2}$ of arity $k$

$\displaystyle((a_{1},b_{1}),\dots,(a_{k},b_{k}))\in
R^{\mathfrak{M}_{i,j}}\Leftrightarrow$ $\displaystyle(\forall
i,j.(a_{i}=a_{j}\Leftrightarrow
b_{i}=b_{j}))\operatorname{\wedge}(b_{1},\dots,b_{k})\in
R^{\mathfrak{B}_{2,j}}.$

Let $\phi_{i}(x_{1},\dots,x_{n})$ be a conjunction of atomic
$\tau_{i}$-formulas for $i=1$ and $i=2$. Notice that forcing $\phi_{1}$ and
$\phi_{2}$ to have the same variables can be done without loss of generality
by introduction of dummy constraints like $x=x$. Suppose there exists a
homomorphism $g\colon
D(\phi_{1}(x_{1},\dots,x_{n})\operatorname{\wedge}\phi_{2}(x_{1},\dots,x_{n}))\rightarrow\mathfrak{A}$
where $\mathfrak{A}$ is a model of $T$. Then $g\colon
D(\phi_{i}(x_{1},\dots,x_{n}))\rightarrow\mathfrak{A}^{\tau_{i}}$ is also a
homomorphism for $i=1$ and $i=2$. As the chosen samplings are equality-
matching, there exists $u_{i}\in[p_{i}]$ and homomorphisms $h_{i}\colon
D(\phi_{i}(x_{1},\dots,x_{n}))\rightarrow\mathfrak{B}_{i,u_{i}}$ for $i=1$ and
$i=2$ such that $h_{1}$ and $h_{2}$ both identify variables in the same way
that $g$ does. Then, by construction,
$x_{i}\mapsto(h_{1}(x_{i}),h_{2}(x_{i}))$ defines a homomorphism from
$D(\phi_{1}\operatorname{\wedge}\phi_{2})$ to $\mathfrak{M}_{u_{1},u_{2}}$
identifying the same variables as $g$.

For the reverse direction suppose that $h$ is a homomomorphism from
$D(\phi_{1}\operatorname{\wedge}\phi_{2})$ to $\mathfrak{M}_{u_{1},u_{2}}$. We
want to show the existence of a homomorphism $g$ from
$D(\phi_{1}\operatorname{\wedge}\phi_{2})$ to $\mathfrak{A}$, where
$\mathfrak{A}$ is a model of $T$ and $g$ and $h$ identify the same variables.
To simplify presentation, we would like to assume that $h$ is injective.
Suppose there exists $x_{i},x_{j}$ such that $h(x_{i})=h(x_{j})$. Then we
replace all occurrences of $x_{j}$ in $\phi_{1}$ and $\phi_{2}$ by $x_{i}$ and
iterate until $h$ is injective on the remaining variables. Call the resulting
formulas $\phi_{1}^{\prime}$ and $\phi_{2}^{\prime}$. If there exists an
injective homomorphism $g$ from
$D(\phi_{1}^{\prime}\operatorname{\wedge}\phi_{2}^{\prime})$ to a model of
$T$, we can extend $g$ to the formerly substituted variables via
$g(x_{j})\coloneqq g(x_{i})$ to get a homomorphism from
$D(\phi_{1}\operatorname{\wedge}\phi_{2})$ to some model of $T$ which has the
same identifications as $h$. Hence, it is sufficient to prove the existence of
$g$ under the assumption that $h$ is injective.

Let $h_{i}\coloneqq\pi_{i}^{2}\circ h$ for $i\in[2]$, where $\pi^{2}_{i}$ is
the projection to the $i$-th coordinate out of of two coordinates. Now suppose
there exists a set $S\subseteq h(D(\phi))$ of size at least two such that any
two elements in $S$ are equal in the first coordinate (the case with the
second coordinate can be proven analogously). Without loss of generality we
will assume $S=\\{h(x_{1}),\dots,h(x_{k})\\}$. Furthermore, we may assume that
$S$ is maximal, i.e., for all $i>k$ we have $h_{1}(x_{i})\neq h_{1}(x_{1})$.
For $i\in[k]$ let $\psi_{i}(x_{i},x_{k+1},\dots,x_{n})$ be the conjunction of
all conjuncts in $\phi_{1}(x_{1},\dots,x_{n})$ which do not contain $x_{j}$
for all $j\in[k]\setminus\\{i\\}$. Then $\phi_{1}$ is equivalent to
$\bigwedge_{i=1}^{k}\psi_{i}(x_{i},x_{k+1},\dots,x_{n})$ because no conjunct
of $\phi_{1}$ can contain more than one variable from $x_{1},\dots,x_{k}$, as
this conjunct would not be satisfied in the image of $h_{1}$ in
$\mathfrak{M}_{u_{1},u_{2}}$. As $T_{1}$ has an equality-matching sampling,
there exists a homomorphism $g_{1}\colon
D(\phi_{1})\rightarrow\mathfrak{A}_{1}$ for some model $\mathfrak{A}_{1}$ of
$T_{1}$, such that $g_{1}$ has the same identifications as $h_{1}$. By the
definition of no pp-algebraicity, the set

$\\{a\in
A\mid\mathfrak{A}_{1}\models\psi_{i}(a,g_{1}(x_{k+1}),\dots,g_{1}(x_{n}))\\}$

is infinite for all $i\in[k]$. Hence, there exists a homomorphism
$g_{1}^{\prime}\colon D(\phi_{1})\rightarrow\mathfrak{A}_{1}$ such that
$g_{1}^{\prime}(x_{i})\neq g_{1}^{\prime}(x_{j})\neq
g_{1}^{\prime}(x_{l})=g_{1}(x_{l})$ for all $i,j\in[k]$ and
$l\in[n]\setminus[k]$. As the sampling for $T_{1}$ is equality-matching, there
exists $u_{1}^{\prime}\in[p_{1}]$ and a homomorphism $h_{1}^{\prime}\colon
D(\phi_{1})\rightarrow\mathfrak{B}_{1,u_{1}^{\prime}}$ with the same
identifications as $g_{1}^{\prime}$. This yields a homomorphism
$x_{i}\mapsto(h_{1}^{\prime}(x_{i}),h_{2}(x_{i}))$ to
$\mathfrak{M}_{u_{1}^{\prime},u_{2}}$ where strictly less variables are mapped
to the same row or column than by $h$.

Iterated application of this argument to $h_{1}$ and, in an analogous way, to
$h_{2}$ proves that there exist injective homomorphisms $h_{1}^{*}$ and
$h_{2}^{*}$ such that $h^{*}$ defined by
$x_{i}\mapsto(h_{1}^{*}(x_{i}),h_{2}^{*}(x_{i}))$ is a homomorphism from
$D(\phi_{1}(x_{1},\dots,x_{n})\operatorname{\wedge}\phi_{2}(x_{1},\dots,x_{2}))$
to $\mathfrak{M}_{u_{1}^{*},u_{2}^{*}}$. As $(O_{n})$ and $(P_{n})$ are
equality-matching samplings there exist injective homomorphisms
$g_{i}^{*}\colon
D(\phi_{i}(x_{1},\dots,x_{n}))\rightarrow\mathfrak{A}_{i}^{*}$ where
$\mathfrak{A}_{i}^{*}$ is a model of $T_{i}$ for $i=1$ and $i=2$. Now observe
that $\mathfrak{A}_{1}^{*}$ and $\mathfrak{A}_{2}^{*}$ are both either empty
(in which case the theorem becomes trivial) or infinite because no pp-
algebraicity implies that $\\{x\mid\mathfrak{A}_{i}^{*}\models x=x\\}$ is
infinite or empty. If $A_{i}^{*}$ is uncountable, then there exists a
$\mathfrak{A}_{i}^{\prime}$ with countable domain such that
$\operatorname{Th}(\mathfrak{A}_{i}^{\prime})=\operatorname{Th}(\mathfrak{A}_{i}^{*})$
due to the Downward Löwenheim-Skolem Theorem (see [13], page 90) and we may
substitute $\mathfrak{A}_{i}^{*}$ by $\mathfrak{A}_{i}^{\prime}$. Hence, we
may assume that $\lvert A_{1}^{*}\rvert=\lvert A_{2}^{*}\rvert$ and therefore,
there exists a bijection $f\colon A_{1}^{*}\rightarrow A_{2}^{*}$ such that
$f(g_{1}^{*}(x_{i}))=g_{2}^{*}(x_{i})$ for all $i\in[n]$. However, any
bijection from $A_{1}^{*}$ to $A_{2}^{*}$ induces a fusion $\mathfrak{A}$ of
$\mathfrak{A}_{1}^{*}$ and $\mathfrak{A}_{2}^{*}$ with domain $A_{1}^{*}$ and
therefore a model of $T$ by Proposition 3.2. Clearly, $g\colon
D(\phi)\rightarrow\mathfrak{A}^{*}$ defined by $g(x_{i})\coloneqq
g_{1}^{*}(x_{i})$ for all $i\in[n]$ is an injective homomorphism. Hence,
$(L_{n})$ with
$L_{n}\coloneqq\\{\mathfrak{M}_{1,1},\dots,\mathfrak{M}_{p_{1},p_{2}}\\}$ is
an equality-matching sampling for $T$.

We have
$|L_{n}\rvert=\sum_{i\in[p_{1}],j\in[p_{2}]}\lvert\mathfrak{B}_{1,i}\rvert\cdot\lvert\mathfrak{B}_{2,j}\rvert=\lvert
O_{n}\rvert\cdot\lvert P_{n}\rvert$ for all $n\in\mathbb{N}$ and to determine
whether a relation $R^{\mathfrak{M}_{i,j}}$ holds on an tuple $t$ requires at
most $n^{2}$ checks for equality and a check if $t\in R^{\mathfrak{B}_{1,i}}$
or $t\in R^{\mathfrak{B}_{2,j}}$. Therefore, if both samplings are computable
in polynomial time, $(L_{n})$ is computable in polynomial time as well. ∎

######  Remark 3.9.

Notice that with almost the same construction, an equality-matching sampling
for any finite number of theories can be constructed as long as all theories
have an equality-matching sampling and only models without pp-algebraicity.
For that we use a higher-dimensional version of the matrix defined in the
proof, where a relation $R\in\tau_{i}$ holds on a tuple $t$ if only if any two
entries of $t$ either differ in all their coordinates or are equal in all
their coordinates and the projection to the $i$-th dimension of each element
of $t$ is in $R$ as defined in the respective sample for $T_{i}$.

Note that if $\mathfrak{A}$ has a finite signature and is without pp-
algebraicity, then all models of $\operatorname{Th}(\mathfrak{A})$ are without
pp-algebraicity. This holds because for each primitive positive formula
$\phi(x_{1},\dots,x_{k})$ and $n\in\mathbb{N}$, the theory
$\operatorname{Th}(\mathfrak{A})$ contains a sentence expressing that for any
choice of parameters $x_{2},\dots,x_{k}$ any satisfying assignment for $x_{1}$
is either equal to one of the parameters or there are at least $n$ different
satisfying assignments for $x_{1}$.

If one of the theories, say $T_{1}$, does not satisfy the conditions of
Theorem 3.8 because it has models with pp-algebraicity, we can prove the
following.

######  Proposition 3.10.

Let $T_{1}$ be a theory with finite relational signature and let
$\mathfrak{A}_{2}$ be an infinite structure with signature $\tau_{2}$ whose
relations are first-order definable over the empty signature. If $T_{1}$ has
an equality-matching sampling $(L_{n})$ and only infinite models, then the
expansion of the samples in $(L_{n})$ with relations in $\tau_{2}$ by their
first-order definitions is an equality-matching sampling for
$T_{1}\cup\operatorname{Th}(\mathfrak{A}_{2})$.

###### Proof.

Fix $n\in\mathbb{N}$ and let $\tau_{1}$ be the signature of $T_{1}$. Call the
expanded sampling $(L_{n}^{\prime})$. Let $\phi_{i}$ be a conjunction of
atomic $\tau_{i}$ formulas. Then $\phi_{2}(x_{1},\dots,x_{n})$ is equivalent
to $\bigvee_{i\in[k]}\psi_{i}(x_{1},\dots,x_{n})$, where each $\psi_{i}$
specifies by a conjunction of equalities and disequalities which variables
must be equal and which must differ . However, for every $i\in[k]$ the formula
$\phi_{1}\operatorname{\wedge}\psi_{i}$ is satisfiable in some element of
$L_{n}$ if and only if it is satisfiable in some model of $T_{1}$ because
$(L_{n})$ is equality-matching. Therefore,
$\phi_{1}\operatorname{\wedge}\phi_{2}$ is satisfiable in some model of
$T_{1}$ if and only if it is satisfiable in some structure in
$L_{n}^{\prime}$. ∎

There are also theories with a sampling but without an equality-matching
sampling: for example, $\mathfrak{A}\coloneqq(\mathbb{Z};R_{a},R_{m})$ where
$R_{a}:=\\{(x,y,z)\mid x+y=z\\}$ and $R_{m}:=\\{(x,y,z)\mid x\cdot y=z\\}$ has
a trivial CSP and therefore a sampling. If there exists an equality-matching
sampling for $\operatorname{Th}(\mathfrak{A})$ we can construct a sampling for
$T\coloneqq\operatorname{Th}(\mathfrak{A})\cup\operatorname{Th}(\mathbb{Z};\neq)$
by Proposition 3.10. Then we can define $z=1$ by the primitive positive
formula $\exists x,y\,(x\cdot z=x\operatorname{\wedge}y\cdot
z=y\operatorname{\wedge}x\neq y)$. It is now easy to see that Hilbert’s tenth
problem, which is undecidable, is many-to-one reducible to
$\operatorname{CSP}(T)$, contradicting Proposition 2.8.

The following example shows that we cannot drop the assumption of no pp-
algebraicity in Theorem 3.8.

######  Example 3.11.

Let $\mathrm{succ}$ be the successor relation on $\mathbb{N}$. Let
$P_{0},P_{1}$ be two disjoint, infinite sets (two colours). Then
$T_{1}\coloneqq\operatorname{Th}(\mathbb{N};\mathrm{succ})$ and
$T_{2}\coloneqq\operatorname{Th}(P_{0}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}P_{1};P_{0},P_{1})$
both have an equality-matching sampling which can be computed in polynomial
time. However, any sampling $(L_{n})_{n\in\mathbb{N}}$ of $T_{1}\cup T_{2}$
has $\lvert L_{n}\rvert\geq 2^{n}$ for all $n\in\mathbb{N}$, and therefore no
polynomial sampling exists.

To prove this, first notice that we can construct a model $\mathfrak{A}$ for
$T\coloneqq T_{1}\cup T_{2}$ such that
$\operatorname{CSP}(\mathfrak{A})=\operatorname{CSP}(T)$. This can be done by
giving each natural number the colour $P_{0}$ or $P_{1}$ in such a way that
the resulting sequence over $\\{0,1\\}$ includes any binary number as
consecutive subsequence. Therefore, when examining lower bounds for $\lvert
L_{n}\rvert$, we may assume by Proposition 2.5 that for each $n$ there is only
one element $\mathfrak{B}_{n}\in S_{n}(T)$ in $L_{n}$. Now observe the
following:

  1. (1)

In any $n$-sample $\mathfrak{B}_{n}$, no element $x$ can satisfy
$P_{0}(x)\operatorname{\wedge}P_{1}(x)$ and there is no pp-formula which can
force a node to have no colour. Hence, if some node in $\mathfrak{B}_{n}$ has
no colour, we can colour this node arbitrarily and the result is again in
$S_{n}(T)$. Therefore, without loss of generality, each node in the sampling
has exactly one colour.

  2. (2)

When we fix a node $c$ in $\mathfrak{B}_{n}$ such that
$\phi_{c}\coloneqq\mathrm{succ}(c,x_{2})\operatorname{\wedge}\dots\operatorname{\wedge}\mathrm{succ}(x_{n-1},x_{n})$
is satisfiable in $\mathfrak{B}_{n}$, then there exists exactly one map
$s\colon[n]\rightarrow\\{0,1\\}$ such that
$\psi_{c,s}\coloneqq\phi_{c}\operatorname{\wedge}\bigwedge_{i\in[n]}P_{s(i)}(x_{i})$
is satisfiable in $\mathfrak{B}_{n}$. If there were two distinct maps $s$ and
$s^{\prime}$, then
$\psi_{x_{1},s}\operatorname{\wedge}\psi_{x_{1},s^{\prime}}$ would be
satisfiable in $\mathfrak{B}_{n}$, but not in $\mathfrak{A}$.

Now observe that atomic $\tau_{1}\cup\tau_{2}$-formulas with $n$ variables can
encode a binary number $b$ of length $n$ via
$\mathrm{succ}(x_{1},x_{2})\operatorname{\wedge}\dots\operatorname{\wedge}\mathrm{succ}(x_{n-1},x_{n})\operatorname{\wedge}\bigwedge_{i\in[n]}P_{b_{i}}(x_{i})$.
By item (2) each element of $\mathfrak{B}_{n}$ is the start of at most one
binary number and therefore, $\mathfrak{B}_{n}$ must have at least $2^{n}$
elements.

We would like to remark that for all $n$ there exists $\mathfrak{B}_{n}\in
S_{n}(T)$ of size $2^{n}$ such that $(\mathfrak{B}_{n})$ is an equality-
matching sampling of $T$. It can be constructed via a de-Brujin sequence.
However, the smallest $n$-universal substructure of a model of $T$ has size
$2^{n}+n-1$, which is larger.

Even though we cannot drop no-pp-algebraicity in general, there are structures
with pp-algebraicity where the sets definable by primitive positive formulas
are somewhat tame and an equality-matching sampling of the union of their
theories exists and is computable in polynomial time. We will demonstrate this
with the following example, which will also occur in the next section.

######  Example 3.12.

Let $E_{1}$ be the relation

$\\{(2a,2a+1),(2a+1,2a)\mid a\in\mathbb{N}\\}.$

Let $E_{2}$ be a copy of $E_{1}$. Then we consider
$T\coloneqq\operatorname{Th}(\mathbb{N};E_{1})\cup\operatorname{Th}(\mathbb{N};E_{2})$.
For $n\in\mathbb{N}$ we will now construct $\mathfrak{B}_{n}\in S_{n}(T)$ such
that $(\mathfrak{B}_{n})_{n\in\mathbb{N}}$ is an equality-matching sampling
for $T$ computable in polynomial time.

Consider formulas $\gamma_{k}$ and $\delta_{k}$ describing an _alternating
sequence_ and an _alternating cycle_ , both of length $2k$, respectively.
Formally, we define $\gamma_{k}(x_{1},\dots,x_{2k+1})$ as the formula
$\bigwedge_{i\in[k]}(E_{1}(x_{2i-1},x_{2i})\operatorname{\wedge}E_{2}(x_{2i},x_{2i+1}))$
and $\delta_{k}(x_{1},\dots,x_{2k})$ as the formula
$\gamma_{k}(x_{1},\dots,x_{2k},x_{1})$.

Let $\mathfrak{B}_{n}$ be the structure containing $\lceil\frac{n}{2k}\rceil$
many copies of $D(\delta_{k}(x_{1},x_{2},\dots,x_{2k}))$, for each
$k\in\\{1,\dots,\lceil\frac{n}{2}\rceil\\}$. Such $\mathfrak{B}_{n}$ has size
in $O(n^{2})$.

We now prove that $(\mathfrak{B}_{n})_{n\in\mathbb{N}}$ is a sampling for $T$.
To this end, note that $\mathfrak{B}_{n}$ can be extended to a model of $T$ by
adding infinitely many alternating cycles of all positive even lengths. We
will now analyze which instances $\phi$ of $\operatorname{CSP}(T)$ are
satisfiable and prove that these are satisfiable in $\mathfrak{B}_{n}$. Let
$\phi_{i}$ be a conjunction of atomic $\tau_{i}$-formulas for $i=1$ and $i=2$
and suppose that $\phi\coloneqq\phi_{1}\operatorname{\wedge}\phi_{2}$ contains
only variables from $\\{x_{1},\dots,x_{n}\\}$ and is satisfiable in some model
of $T$. If $\phi$ contains conjuncts of the form
$E_{i}(x,y)\operatorname{\wedge}E_{i}(y,z)$ then $x=z$ must hold in any model
of $T$. Hence, we may simplify our analysis by replacing $z$ by $x$ in $\phi$.
The instance $E_{i}(x,x)$ is never satisfiable. Therefore, if $\phi$ contains
the conjunct $E_{i}(x,y)$ then $x$ and $y$ do not appear in any other $E_{i}$
conjunct, i.e., each variable appears at most once in all $E_{1}$ conjuncts
and at most once in all $E_{2}$ conjuncts. Hence, $\phi$ can only describe
alternating sequences and alternating cycles, both of which homomorphically
map into alternating cycles of suitable length and therefore to
$\mathfrak{B}_{n}$.

##  4\. Exemplary Application to CSPs

We finally show how to use the sampling $(L_{n})$ constructed in Theorem 3.8
in order to prove the polynomial-time tractability of
$\operatorname{CSP}(T_{1}\cup T_{2})$. To do this, we use algorithms for the
CSPs of the structures $\mathfrak{B}_{n}\in L_{n}$ which run in _uniform_
polynomial time, i.e., the runtime is polynomial in the size of the instance
and in $\lvert B_{n}\rvert$. The following generalises a result for CSPs of
structures by Bodirsky, Macpherson, and Thapper [6] to CSPs of theories.

######  Proposition 4.1.

Let $T$ be a theory with finite relational signature and let $(L_{n})$ be a
sampling of $T$ computable in polynomial time. If there is an algorithm that
solves $\operatorname{CSP}(\mathfrak{B}_{n})$ for every $\mathfrak{B}_{n}\in
L_{n}$ in uniform polynomial time, then $\operatorname{CSP}(T)$ is polynomial-
time tractable.

###### Proof.

To decide an instance $\phi$ of $\operatorname{CSP}(T)$ on $n$ variables we
run the algorithm on $(\mathfrak{B},\phi)$ for all $\mathfrak{B}\in L_{n}$. If
the algorithm accepts on any of these tuples, we return ‘satisfiable’,
otherwise we return ‘unsatisfiable’. This is correct and complete by the
definition of sampling. Furthermore, the procedure runs in polynomial time,
because $|L_{n}|$ is polynomial in $n$ and the algorithms worst-case runtime
is polynomial in $n$ and $|L_{n}|$ and therefore polynomial in $n$. ∎

To describe classes of finite structures whose CSP can be be solved by a
uniform polynomial-time algorithm, the following concepts from universal
algebra are important.

######  Definition 4.2.

Let $\mathfrak{A}$ be a relational structure with signature $\tau$ and let $f$
be an operation of arity $k$ on $\mathfrak{A}$. We call $f$ a _polymorphism_
of $\mathfrak{A}$ if it is a homomorphism from $\mathfrak{A}^{k}$ to
$\mathfrak{A}$, i.e., whenever $t_{1},\dots,t_{k}\in R^{\mathfrak{A}}$, for
some $R\in\tau$, then $f(t_{1},\dots,t_{k})\in R^{\mathfrak{A}}$, where $f$ is
applied componentwise. An operation $f\colon A^{k}\rightarrow A$ is _totally
symmetric_ if for all $x_{1},\dotsc,x_{k},y_{1},\dotsc,y_{k}\in A$ we have
$f(x_{1},\dotsc,x_{k})=f(y_{1},\dotsc,y_{k})$ whenever
$\\{x_{1},\dotsc,x_{k}\\}=\\{y_{1},\dotsc,y_{k}\\}$. If $k\geq 3$ and for all
$a,b\in A$ we have
$f(a,b,b,\dots,b)=f(b,a,b,b,\dots,b)=\dots=f(b,b,\dots,b,a)=b$, then $f$ is
called a _near-unanimity operation_.

######  Proposition 4.3 (Corollary 3.6 in [14]).

There is an algorithm that solves $\operatorname{CSP}(\mathfrak{B})$ in
uniform polynomial time for all finite relational structures $\mathfrak{B}$
with a near-unanimity polymorphism.

Results about the applicability of fast uniform algorithms for CSPs of finite
relational structures with a near-unanimity polymorphism can be found in the
work of Kozik (2016).

Proposition 4.3 and Proposition 4.1 can be applied to Example 3.12 with the
following near-unanimity operation $f$ defined on $\mathfrak{B}_{n}$ for
$n\in\mathbb{N}$:

$f(x,y,z)\coloneqq\left\\{\begin{array}[]{ll}y&\text{if }y=z,\\\
x&\text{otherwise.}\end{array}\right.$

Note that $f$ is a polymorphism of $\mathfrak{B}_{n}$, for all $n$, because if
$(t_{1,1},t_{1,2})$, $(t_{2,1},t_{2,2})$ and $(t_{3,1},t_{3,2})$ are in
$E_{k}$ and $t_{i,1}=t_{j,1}$, then $t_{i,2}=t_{j,2}$ and therefore
$f(t_{1},t_{2},t_{3})=(t_{i,1},t_{i,2})\in E_{k}$ for all
$k\in[2],i,j\in[3],i\neq j$. In particular, $\operatorname{CSP}(T)$ with $T$
from Example 3.12 can be solved in polynomial time.

An example for a totally symmetric polymorphism is the minimum operation over
$(\mathbb{Q};<)$. Also, we can define minimum as an operation of any arity.
The following result builds on results of Feder and Vardi [11].

######  Theorem 4.4 (Section 3 in [9]).

Let $\mathfrak{B}$ be a finite structure with finite relational signature.
Then the arc-consistency procedure solves $\operatorname{CSP}(\mathfrak{B})$
iff $\mathfrak{B}$ has totally symmetric polymorphisms of all arities.

The Arc-consistency algorithm runs in worst-case time $O(n^{2}m^{2})$ where
$n$ is the number of variables in the instance and $m$ is the size of the
domain [8]. Theorem 4.4 and Proposition 4.1 immediately yield the following.

######  Corollary 4.5.

Let $(L_{n})$ be a sampling for $T$ which is computable in polynomial time. If
all samples in $(L_{n})$ have totally symmetric polymorphism of all arities,
then $\operatorname{CSP}(T)$ is polynomial-time tractable.

We can slightly relax the requirement that all the structures in $L_{n}$ have
totally symmetric polymorphisms.

######  Lemma 4.6.

Let $T$ be a theory with finite relational signature and let $(L_{n})$ be a
sampling of $T$ computable in polynomial time. If for all $n\in\mathbb{N}$ and
all $\mathfrak{B}\in L_{n}$ there exists a model $\mathfrak{A}_{\mathfrak{B}}$
of $T$ and a homomorphism
$h\colon\mathfrak{B}\rightarrow\mathfrak{A}_{\mathfrak{B}}$ such that
$h(\mathfrak{B})$ has totally symmetric polymorphisms of all arities, then
$\operatorname{CSP}(T)$ is polynomial-time tractable.

###### Proof.

To decide an instance with $n$ variables, we run arc-consistency on each pair
$(\mathfrak{B},\phi)$ where $\phi$ is the instance and $\mathfrak{B}\in
L_{n}$. Whenever arc-consistency returns ‘unsatisfiable’ for an instance on a
structure $\mathfrak{B}$, the instance is unsatisfiable in $\mathfrak{B}$
(this holds for any finite structure). Hence, if all runs reject, the instance
is unsatisfiable.

Suppose that the arc-consistency procedure returned ‘satisfiable’ on
$(\mathfrak{B},\phi)$. Then, the algorithm produced for each variable a non-
empty list of values in $\mathfrak{B}$ such that no list can be shortened due
to constraints in the instance. Thus, when we apply $h$ to all these values,
we gain non-empty lists of values over $\mathfrak{A}_{\mathfrak{B}}$ where all
relations that did hold in $\mathfrak{B}$ hold again. Hence, arc-consistency
cannot return ‘unsatisfiable’ when run on the image of $h$. By Theorem 4.4,
this means that the instance is satisfiable on the image of $h$, therefore in
$\mathfrak{A}_{\mathfrak{B}}$ and therefore in some element of $(L_{n})$, by
definition of sampling. As $(L_{n})$ is computable in polynomial time and arc-
consistency runs in uniform polynomial time, we can decide
$\operatorname{CSP}(T)$ in polynomial time. ∎

We conclude this section with a concrete reasoning task that can be solved in
polynomial time with our methods, and that is not covered by the combination
results of Nelson and Oppen [17, 18] .

######  Example 4.7.

Given parts of a huge machine, each of which can be mounted by exactly one of
two robots, and precedence constraints on the order in which parts can be
mounted, calculate a possible order in which the machine can be assembled.
Some parts must be mounted by one robot, some by the other robot, and some
parts can be mounted by both robots. The two robots are not allowed to work
simultaneously. This reasoning task can be modelled as
$\operatorname{CSP}(T_{1}\cup T_{2})$ where

  * •

$T_{1}:=\operatorname{Th}(\mathfrak{A}_{1})$ for a first-order expansion
$\mathfrak{A}_{1}$ of $(\mathbb{Q};<)$ that allows to model the precedence
constraints, and

  * •

$T_{2}:=\operatorname{Th}(\mathfrak{A}_{2})$ where $\mathfrak{A}_{2}$ has two
disjoint countably infinite unary relations and their union as domain.

By Lemma 3.5 and Lemma 3.6, the theories $T_{1}$ and $T_{2}$ have polynomial-
time computable samplings, and both structures have no pp-algebraicity. Hence,
by Theorem 3.8 there exists a polynomial-time computable sampling $(L_{n})$
for $T_{1}\cup T_{2}$. Let $\tau_{i}$ be the signature of $\mathfrak{A}_{i}$,
for $i\in\\{1,2\\}$. For every $n\in{\mathbb{N}}$ and every
$\mathfrak{C}_{n}\in L_{n}$ there exists an injective homomorphism $h_{1}$
from $\mathfrak{C}_{n}^{\tau_{1}}$ to $\mathfrak{A}_{1}$ and an injective
homomorphism $h_{2}$ from $\mathfrak{C}_{n}^{\tau_{2}}$ to $\mathfrak{A}_{2}$;
this follows by inspection of the construction of $\mathfrak{C}_{n}$ in the
proof of Theorem 3.8 and the proofs of Lemma 3.5 and Lemma 3.6. As
$\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ are both countably infinite and
$h_{1}$ and $h_{2}$ are injective, there exists a bijection $f$ between
$A_{1}$ and $A_{2}$ such that $f(h_{1}(a))=h_{2}(a)$ for all $a\in C_{n}$,
inducing a fusion $\mathfrak{A}$ of $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$.
By construction of $\mathfrak{A}$, the map $h_{1}$ is a homomorphism from
$\mathfrak{C}_{n}$ to $\mathfrak{A}$.

Also note that the minimum operation is a polymorphism of all unary relations.
Hence, if $\mathfrak{A}_{1}$ has the minimum operation as a polymorphism then
the minimum operation is also a polymorphism of $\mathfrak{A}$. Then Lemma 4.6
implies that $\operatorname{CSP}(T_{1}\cup T_{2})$ is polynomial-time
tractable.

An example for such a structure $\mathfrak{A}_{1}$ is
$\mathfrak{A}_{1}\coloneqq(\mathbb{Q};<,R)$ where $R$ is the ternary relation
defined by $R(x,y,z)\Leftrightarrow x=\min(y,z)$; it is easy to check that the
minimum operation is a polymorphism of $\mathfrak{A}_{1}$. This example is not
covered by the conditions of Nelson and Oppen, since
$\operatorname{Th}(\mathfrak{A}_{1})$ is _not convex_ : the formula
$R(x,y,z)\wedge x\neq y$ is satisfiable, the formula $R(x,y,z)\wedge y\neq z$
is satisfiable, but the formula $R(x,y,z)\wedge x\neq y\wedge y\neq z$ is not
satisfiable in $\mathfrak{A}_{1}$.

We mention that the polynomial-time tractability of
$\operatorname{CSP}(\mathfrak{A}_{1})$ for
$\mathfrak{A}_{1}=({\mathbb{Q}};<,R)$ in our example was already known in the
SMT community [3]. It is straightforward to generalise the example to any
finite number $m$ of robots, by replacing the structure $\mathfrak{A}_{2}$ by
the structure $({\mathbb{Q}};P_{1},\dots,P_{m})$ that we have already
encountered in Lemma 3.6.

## References

  * [1] Noga Alon  “Asymptotically optimal induced universal graphs”  In _Geometric and Functional Analysis_ 27.1 Birkhauser Verlag Basel, 2017  DOI: 10.1007/s00039-017-0396-9
  * [2] Franz Baader and Klaus Schulz  “Combining Constraint Solving”  In _H. Comon, C. March, and R. Treinen, editors, Constraints in Computational Logics_ , LNCS 2002  Springer-Verlag, 2001
  * [3] Marc Bezem, Robert Nieuwenhuis and Enric Rodríguez-Carbonell  “The Max-Atom Problem and Its Relevance”  In _Proceedings of the International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR)_ , 2008, pp. 47–61
  * [4] Manuel Bodirsky and Johannes Greiner  “The Complexity of Combinations of Qualitative Constraint Satisfaction Problems”  In _Logical Methods in Computer Science_ Volume 16, Issue 1, 2020  URL: https://lmcs.episciences.org/6129
  * [5] Manuel Bodirsky and Martin Grohe  “Non-dichotomies in Constraint Satisfaction Complexity”  In _Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP)_ , Lecture Notes in Computer Science  Springer Verlag, 2008, pp. 184–196
  * [6] Manuel Bodirsky, Dugald Macpherson and Johan Thapper  “Constraint Satisfaction Tractability from Semi-lattice Operations on Infinite Sets”  In _Transaction of Computational Logic (ACM-TOCL)_ 14.4, 2013, pp. 1–30
  * [7] Manuel Bodirsky and Jaroslav Nešetřil  “Constraint Satisfaction with Countable Homogeneous Templates”  In _Journal of Logic and Computation_ 16.3, 2006, pp. 359–373
  * [8] Martin C. Cooper  “An optimal k-consistency algorithm”  In _Artificial Intelligence_ 41.1, 1989, pp. 89–95  DOI: 10.1016/0004-3702(89)90080-5
  * [9] Víctor Dalmau and Justin Pearson  “Closure Functions and Width 1 Problems”  In _Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP)_ , 1999, pp. 159–173
  * [10] Leonardo De Moura and Nikolaj Bjørner  “Satisfiability modulo Theories: Introduction and Applications”  In _Communications of the ACM_ 54.9 New York, NY, USA: Association for Computing Machinery, 2011, pp. 69–77  DOI: 10.1145/1995376.1995394
  * [11] Tomás Feder and Moshe Y. Vardi  “The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory”  In _SIAM Journal on Computing_ 28, 1999, pp. 57–104
  * [12] Mark K. Gol’dberg and Emmanuel M. Livshits  “On Minimal Universal Trees”  In _Mathematical Notes of the Academy of Sciences of the USSR_ 4, 1968, pp. 713–717  DOI: 10.1007/BF01116454
  * [13] Wilfrid Hodges  “Model theory”  Cambridge University Press, 1993
  * [14] Peter Jeavons, David Cohen and Martin Cooper  “Constraints, Consistency and Closure”  In _Artificial Intelligence_ 101.1-2, 1998, pp. 251–265
  * [15] Vadim Lozin and Gabor Rudolf  “Minimal Universal Bipartite Graphs.”  In _Ars Combinatoria_ 84, 2007
  * [16] J.. Moon  “On minimal n-universal graphs”  In _Proceedings of the Glasgow Mathematical Association_ 7.1 Cambridge University Press, 1965, pp. 32–33  DOI: 10.1017/S2040618500035139
  * [17] Greg Nelson and Derek C. Oppen  “Simplification by Cooperating Decision Procedures”  In _ACM Transactions on Programming Languages and Systems_ 1.2 New York, NY, USA: ACM, 1979, pp. 245–257  DOI: 10.1145/357073.357079
  * [18] Derek C. Oppen  “Complexity, convexity and combinations of theories”  In _Theoretical Computer Science_ 12.3, 1980, pp. 291–302  DOI: 10.1016/0304-3975(80)90059-6
  * [19] Klaus U. Schulz  “Why Combined Decision Problems Are Often Intractable”  In _Frontiers of Combining Systems_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2000, pp. 217–244
  * [20] Cesare Tinelli and Christophe Ringeissen  “Unions of non-disjoint theories and combinations of satisfiability procedures”  In _Theoretical Computer Science_ 290.1, 2003, pp. 291–353  DOI: 10.1016/S0304-3975(01)00332-2