Suppose that $\mathfrak{D}$ has a finite relational signature and for every
$i\in\\{1,2\\}$, the clone $\operatorname{Pol}(\mathfrak{D})$ contains an
operation $f_{i}$ such that $\theta_{i}(f_{i})$ is an
$\operatorname{ll}$-operation. Then $\operatorname{CSP}(\mathfrak{D})$ can be
solved in polynomial time.

###### Proof.

The structure $\mathfrak{D}$ has a primitive positive interpretation in
$\mathfrak{L}$ by Proposition 56. The result follows from Lemma 9 since
$\operatorname{CSP}(\mathfrak{L})$ can be solved in polynomial time. ∎

We will use some additional observations and notations in the proof of the
next proposition (and also in its generalisation Proposition 63). Assume that
the relational structure $\mathfrak{A}$ with domain ${\mathbb{Q}}$ has a
finite signature and there is an $\operatorname{ll}$-operation in
$\operatorname{Pol}(\mathfrak{A})$. We know from Theorem 29 that
CSP$(\mathfrak{A})$ is polynomial-time solvable. Assume now that
$\mathfrak{A}^{\prime}$ is a solvable instance of
$\operatorname{CSP}(\mathfrak{A})$ with variable set $X$. The polynomial-time
algorithm for $\operatorname{CSP}(\mathfrak{A})$ by Bodirsky and Kára [BK10,
Section 4] computes additional information in the form of an equality set: a
set $E\subseteq X^{2}$ such that for every $(x,x^{\prime})\in E$ and every
solution $s$, it holds that $s(x)=s(x^{\prime})$. Furthermore, there exists a
solution $t$ such that $t(x)\neq t(x^{\prime})$ for every
$(x,x^{\prime})\not\in E$.

With this in mind, we introduce the following notation. Let $X$ be a set of
variables, $S\subset\\{1,\dots n\\}$ and $E\subseteq\\{(x^{i},y^{i})\mid
x,y\in X,i\in S\\}$ where $x^{i},y^{i}$ denote fresh variables. Assume $\phi$
is a formula over $(\mathbb{Q}^{n},<_{1},=_{1},\dots,<_{n},=_{n})$ that only
uses the variables in $X$. If $\phi$ equals
$\bigwedge_{p\in\\{1,\dots,n\\}\setminus S}{\phi_{p}}\wedge\phi_{S}$, where
$\phi_{p}$ is a conjunction of $S$-weakly $p$-determined clauses for each $p$
and $\phi_{S}$ is a conjunction of $S$-determined clauses, then we let
$\operatorname{cm}(\phi,E)$ (for clause modification) denote the formula
resulting from $\phi$ by performing the following procedure for each
$p\in\\{1,\dots,n\\}\setminus S$:

  * •

If $(x^{i},y^{i})\in E$ and $\phi_{p}$ contains a clause with the literal
$x\neq_{i}y$, then remove this literal from the clause and add the conjunct
$x=_{i}y$.

  * •

If $(x^{i},y^{i})\not\in E$ and $\phi_{p}$ contains a clause with the literal
$x\neq_{i}y$, then delete all literals in the clause but this one.

The following proposition and its proof describe a polynomial time algorithm
for $\operatorname{CSP}(\mathfrak{D})$, where
$\operatorname{Pol}(\mathfrak{D})$ satisfies certain conditions. A generalised
version of this algorithm for first-order expansions of $(\mathbb{Q},<)^{(n)}$
with $n\geq 2$ will be presented in Proposition 63 and Algorithm 1. There are
no profound differences between the algorithms but the case when $n=2$ is
easier to present since we can keep the formal machinery at a minimum.

######  Proposition 58.

Suppose that $\mathfrak{D}$ has a finite relational signature and that
$\operatorname{Pol}(\mathfrak{D})$ contains $f_{1},f_{2}$ such that
$\theta_{1}(f_{1})$ equals $\min_{3}$, $\operatorname{mx}_{3}$, or
$\operatorname{mi}_{3}$, and $\theta_{2}(f_{2})$ is an
$\operatorname{ll}$-operation. Then $\operatorname{CSP}(\mathfrak{D})$ can be
solved in polynomial time.

###### Proof.

Apply Lemma 40 to the operation $f_{1}$ for dimension $i=2$. Then, there is an
operation $f_{1}^{\prime}\in\operatorname{Pol}(\mathfrak{D})$ such that
$\theta_{2}(f_{1}^{\prime})$ is canonical over
$\operatorname{Aut}(\mathbb{Q};<)$ and $m:=\theta_{1}(f_{1}^{\prime})$ equals
$\min_{3}$, $\operatorname{mx}_{3}$, or $\operatorname{mi}_{3}$. By Lemma 41,
$f_{1}^{\prime}$ preserves $\neq_{2}$. Since $\theta_{2}(f_{2})$ is an
$\operatorname{ll}$-operation, $f_{2}$ preserves $\neq_{2}$ as well. Therefore
we may assume without loss of generality that $\mathfrak{D}$ contains the
relation $\neq_{2}$. Since $\theta_{1}(\operatorname{Pol}(\mathfrak{D}))$ is
closed (by Proposition 17), it follows from Proposition 32 that
$\theta_{1}(\operatorname{Pol}(\mathfrak{D}))$ contains a
$\operatorname{pp}$-operation.

Let $\tau$ be the signature of $\mathfrak{D}$ and let $\mathfrak{A}$ be an
instance of $\operatorname{CSP}(\mathfrak{D})$. For every $R\in\tau$ of arity
$k$ and $\bar{a}=(a_{1},\dots,a_{k})\in R^{\mathfrak{A}}$, let
$\phi_{R,\bar{a}}$ be the first-order definition of $R$ in
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$, using the elements
$a_{1},\dots,a_{k}$ as free variables. Since
$\theta_{1}(\operatorname{Pol}(\mathfrak{D}))$ contains a
$\operatorname{pp}$-operation and
$\theta_{2}(\operatorname{Pol}(\mathfrak{D})$ contains an
$\operatorname{ll}$-operation, we may assume that $\phi_{R,\bar{a}}$ has the
form described in Proposition 54. Let
$\Phi=\\{\phi_{R,\bar{a}}\;|\;R\in\tau\text{ and }\bar{a}\in
R^{\mathfrak{A}}\\}$. The set $\Phi$ can be computed in polynomial time since
$\mathfrak{D}$ has a finite signature. It is clear that $\mathfrak{A}$ is a
yes-instance of $\operatorname{CSP}(\mathfrak{D})$ if and only if $\Phi$ is
satisfiable. We will now present a polynomial-time algorithm for checking the
satisfiability of $\Phi$. The basic idea is to compute two sets $\Psi_{1}$ and
$\Psi_{2}$ of logical formulas that are simultaneously satisfiable if and only
if $\Phi$ is satisfiable. The sets $\Psi_{1}$ and $\Psi_{2}$ are, in a sense
that will be clarified below, connected to formulas in $\Phi$ that contain
weakly 1-determined and 2-determined clauses, respectively.

Every $\phi\in\Phi$ is of the form $\phi_{1}\wedge\psi_{2}$, where $\phi_{1}$
is a conjunction of weakly $1$-determined clauses and $\psi_{2}$ is a
conjunction of clauses of the form

$x_{1}\neq_{2}y_{1}\vee\cdots\vee x_{m}\neq_{2}y_{m}\vee
z_{1}<_{2}z_{0}\vee\cdots\vee
z_{\ell}<_{2}z_{0}\vee(z_{0}=_{2}z_{1}=_{2}\cdots=_{2}z_{\ell}).$

Therefore $\hat{\psi_{2}}$ is a conjunction of $\operatorname{ll}$-Horn
clauses and by Theorem 38 preserved by an $\operatorname{ll}$-operation. We
let $\Psi_{2}$ denote the set of all formulas $\hat{\psi}_{2}$ obtained in
this way from the members of $\Phi$. Note that $\Psi_{2}$ can be computed in
polynomial time since $\mathfrak{D}$ has a finite relational signature.

Since $\Psi_{2}$ is preserved by an $\operatorname{ll}$-operation, we can
check its satisfiability in polynomial time by Theorem 38 combined with
Theorem 29. If $\Psi_{2}$ is not satisfiable, then we reject the input
$\mathfrak{A}$. Otherwise, we let $E^{\prime}$ denote the equality set of the
instance. For each $(x,y)\in E^{\prime}$, we put a pair $(x^{2},y^{2})$ in the
set $E$; this set will later on be used as an argument to the clause
modification operator $\operatorname{cm}(\cdot)$ that was introduced in
connection with Proposition 58.

Every $\phi$ in $\Phi$ is equivalent to a formula $\phi_{1}\wedge\psi_{2}$ as
described above. Let $S=\\{2\\}$ and note that the formula
$\phi_{1}\wedge\psi_{2}$ admits application of the clause modification
operator $\operatorname{cm}(\cdot)$. Hence, we define $\Phi^{\prime}$ to be
the set of the formulas $\operatorname{cm}(\phi_{1}\wedge\psi_{2},E)$ obtained
from formulas $\phi\in\Phi$. Note that each formula in $\Phi^{\prime}$ still
defines a relation that has a primitive positive definition in $\mathfrak{D}$
(since $\mathfrak{D}$ contains the relations $=_{2}$ and $\neq_{2}$). Further
note that, up to renaming variables, only finitely many different formulas may
appear in $\Phi^{\prime}$: there are only finitely many inequivalent ways to
remove $\neq_{2}$-literals or clauses with such literals and to add $=_{2}$\-
or $\neq_{2}$-conjuncts to the formulas $\phi_{1}\wedge\psi_{2}$ defining one
of the finitely many relations in $\mathfrak{D}$.

Every weakly $1$-determined clause of a formula in $\Phi^{\prime}$ that does
not contain a literal $x\neq_{2}y$ is $1$-determined. Every
$\phi^{\prime}\in\Phi^{\prime}$ can thus be written as
$\phi_{1}^{\prime}\wedge\phi_{2}^{\prime}$, where $\phi_{i}^{\prime}$ is a
conjunction of $i$-determined clauses. It follows that $\phi^{\prime}$ is
equivalent to $\psi_{1}^{\prime}\wedge\phi_{2}^{\prime}$ where
$\psi_{1}^{\prime}=\operatorname{cr}(\phi^{\prime},\\{1\\},\phi_{1}^{\prime})$.
Note that $\psi_{1}^{\prime}$ is preserved by
$\operatorname{Pol}(\mathfrak{D})$. Since $\mathfrak{D}$ has finite relational
signature, there are only finitely many inequivalent formulas that can arise
in this way so the formulas $\psi_{1}^{\prime}$ can be computed in polynomial
time: they can simply be stored in a fixed-size database that is computed off-
line. By Lemma 21, $\hat{\psi}_{1}^{\prime}$ is preserved by the operation
$m\in\theta_{1}(\operatorname{Pol}(\mathfrak{D}))$. Let $\Psi_{1}$ be the set
of all formulas $\hat{\psi}_{1}^{\prime}$ obtained from $\Phi^{\prime}$ in
this way. We may use the algorithmic part of Theorem 29 to decide whether
$\Psi_{1}$ is satisfiable. If $\Psi_{1}$ is not satisfiable, then we reject
the input $\mathfrak{A}$ and we accept it otherwise. We claim that in this
case $\Phi$ is satisfiable and, consequently, that $\mathfrak{A}$ has a
homomorphism to $\mathfrak{D}$.

Indeed, let $s\colon A\to{\mathbb{Q}}$ be a solution to $\Psi_{1}$ and let
$t\colon A\to{\mathbb{Q}}$ be a solution to $\Psi_{2}$. Since $\mathfrak{D}$
is preserved by an operation $g$ such that $\theta_{2}(g)$ is an
$\operatorname{ll}$-operation, and $\operatorname{ll}$-operations are
injective, we may assume that $t$ satisfies $x\neq_{2}y$ unless this literal
has been removed from $\Phi$ by the algorithm. Then the map
$x\mapsto(s(x),t(x))$ satisfies all formulas in $\Phi$ and it follows that
$\mathfrak{A}$ admits a homomorphism to $\mathfrak{D}$. ∎

###  4.5 Classification in the 2-Dimensional Case

The known results about first-order expansions of $({\mathbb{Q}};<)$ from
Section 4.1 combined with the results from Section 4.3 imply an algebraic
dichotomy for polymorphism clones of first-order expansions of
$(\mathbb{Q}^{2};<_{1},=_{1},<_{2},=_{2})$; the algebraic dichotomy implies a
complexity dichotomy, using the results from Section 4.4.

######  Theorem 59.

Exactly one of the following two cases applies.

  * •

For each $i\in\\{1,2\\}$ we have that
$\theta_{i}(\operatorname{Pol}(\mathfrak{D}))$ contains $\min_{3}$,
$\operatorname{mx}_{3}$, $\operatorname{mi}_{3}$, or $\operatorname{ll}_{3}$,
or one of their duals. Furthermore, $\mathfrak{D}$ has a pwnu polymorphism and
if $\mathfrak{D}$ has a finite relational signature, then
$\operatorname{CSP}(\mathfrak{D})$ is in P.

  * •

$\operatorname{Pol}(\mathfrak{D})$ has a uniformly continuous minor-preserving
map to $\operatorname{Pol}(K_{3})$. In this case, $\mathfrak{D}$ has a finite
signature reduct whose $\operatorname{CSP}$ is NP-complete.

###### Proof.

For $i\in\\{1,2\\}$, let
${\mathscr{C}}_{i}=\theta_{i}(\operatorname{Pol}(\mathfrak{D}))$. If
${\mathscr{C}}_{i}$, for some $i\in\\{1,2\\}$, has a uniformly continuous
minor-preserving map from ${\mathscr{C}}_{i}$ to $\operatorname{Pol}(K_{3})$,
then by composing uniformly continuous minor-preserving maps there is also a
uniformly continuous minor-preserving map from
$\operatorname{Pol}(\mathfrak{D})$ to $\operatorname{Pol}(K_{3})$, which
implies that $\mathfrak{D}$ has a finite signature reduct whose
$\operatorname{CSP}$ is NP-hard by Corollary 12. Assume henceforth that there
is no uniformly continuous minor-preserving map from $\mathscr{C}_{i}$ to
$\operatorname{Pol}(K_{3})$.

Let $\mathfrak{D}_{i}$ be the structure with domain ${\mathbb{Q}}$ that
contains all relations that are preserved by ${\mathscr{C}}_{i}$; note that
$\operatorname{Pol}(\mathfrak{D}_{i})={\mathscr{C}}_{i}$ by Proposition 17.
Clearly, ${\mathscr{C}}_{i}$ contains $\operatorname{Aut}({\mathbb{Q}};<)$ and
preserves $<$, so $\mathfrak{D}_{i}$ is a first-order expansion of
$({\mathbb{Q}};<)$. By Theorem 29, $\mathscr{C}_{i}$ contains $\min_{3}$,
$\operatorname{mx}_{3}$, $\operatorname{mi}_{3}$, or $\operatorname{ll}_{3}$,
or the dual of one of these operations. By Lemma 45, we may assume that
$\mathscr{C}_{i}$ contains an operation
$f_{i}\in\\{\min_{3},\operatorname{mx}_{3},\operatorname{mi}_{3},\operatorname{ll}_{3}$};
we assume without loss of generality that $f_{i}=\operatorname{ll}_{3}$
whenever $\mathscr{C}_{i}$ contains $\operatorname{ll}_{3}$. If
${\mathscr{C}}_{i}$, for some $i\in\\{1,2\\}$, contains a
$\operatorname{lex}$-operation, then ${\mathscr{C}}_{i}$ contains
$\operatorname{ll}_{3}$: otherwise,
$\theta_{i}(\operatorname{Pol}(\mathfrak{D}))$ would have to contain
$\operatorname{mi}_{3}$, $\operatorname{mx}_{3}$, or $\operatorname{mi}_{3}$,
and by Proposition 32 a $\operatorname{pp}$-operation. It then follows from
the final statement in Theorem 38 that ${\mathscr{C}}_{i}$ contains
$\operatorname{ll}_{3}$ and this contradicts our assumptions.

Assume that ${\mathscr{C}}_{2}$ contains $\operatorname{ll}_{3}$, and hence an
$\operatorname{ll}$-operation by Theorem 38. If ${\mathscr{C}}_{1}$ contains
$\min_{3}$, $\operatorname{mi}_{3}$, or $\operatorname{mx}_{3}$, then the
polynomial-time tractability of $\operatorname{CSP}(\mathfrak{D})$ follows
from Proposition 58. Otherwise, ${\mathscr{C}}_{1}$ contains
$\operatorname{ll}_{3}$ (and hence an $\operatorname{ll}$-operation by Theorem
38) and the polynomial-time tractability of $\operatorname{CSP}(\mathfrak{D})$
follows from Proposition 57. The case when $\mathscr{C}_{1}$ contains
$\operatorname{ll}_{3}$ follows from the same argument with the roles of the
two dimensions exchanged.

Suppose in the following that neither ${\mathscr{C}}_{1}$ nor
${\mathscr{C}}_{2}$ contains a $\operatorname{lex}$-operation. Remark 37
combined with Theorem 38 imply that they do not contain the operation
$\operatorname{ll}_{3}$. Then, both ${\mathscr{C}}_{1}$ and
${\mathscr{C}}_{2}$ contain $\min_{3}$, $\operatorname{mi}_{3}$, or
$\operatorname{mx}_{3}$, and Proposition 32 imply that both
${\mathscr{C}}_{1}$ and ${\mathscr{C}}_{2}$ contain a
$\operatorname{pp}$-operation. By Proposition 55, every relation of
$\mathfrak{D}$ can be defined by a conjunction of $1$-determined clauses and
of $2$-determined clauses. Thus, Lemma 22 implies that
$\operatorname{Pol}(\mathfrak{D})$ contains
${\mathscr{C}}_{1}\times{\mathscr{C}}_{2}$. Then the polynomial-time
tractability of $\operatorname{CSP}(\mathfrak{D})$ follows from Corollary 19
applied to $\mathfrak{A}_{1},\mathfrak{A}_{2}$, and $\mathfrak{D}$.

We continue by proving that $\mathfrak{D}$ admits a pwnu polymorphism. Let $f$
be the ternary operation such that $\theta_{i}(f)$ equals $f_{i}$ for every
$i\in\\{1,2\\}$. We claim that $f$ preserves $\mathfrak{D}$. Let $\phi$ be a
formula that defines a relation from $\mathfrak{D}$. By Proposition 50, we may
assume that $\phi$ is a normal conjunction of clauses each of which is weakly
$i$-determined for some $i$. Let $a,b,c$ be tuples that satisfy $\phi$. Let
$\psi$ be a clause of $\phi$. We may assume that $\psi$ is weakly
$2$-determined, since the case where it is weakly $1$-determined can be
treated analogously. Then $\psi$ is of the form
$\psi^{\prime}\vee\psi^{\prime\prime}$, where $\psi^{\prime}$ is a
$2$-determined clause and $\psi^{\prime\prime}$ is a disjunction of
$\neq_{1}$-literals. We show that $f(a,b,c)$ satisfies $\psi$.

Note that it follows from the discussion above that $\mathscr{C}_{i}$ contains
for each $i\in\\{1,2\\}$ a $\operatorname{pp}$-operation or an
$\operatorname{ll}$-operation. If $\psi$ contains a literal $x\neq_{1}y$, then
it is not $2$-determined and it follows from Proposition 55 that either
$\mathscr{C}_{1}$ does not contain a $\operatorname{pp}$-operation or
$\mathscr{C}_{2}$ contains a $\operatorname{lex}$-operation. In the first
case, $\mathscr{C}_{1}$ does not contain $\min_{3}$, $\operatorname{mx}_{3}$
or $\operatorname{mi}_{3}$ by Proposition 32 so $f_{1}=\operatorname{ll}_{3}$.
In the second case, Proposition 51 implies that $\psi$ is weakly
$1$-determined. We see that $f_{2}=\operatorname{ll}_{3}$ by Theorem 38 since
either (1) $\mathscr{C}_{2}$ simultaneously contains a
$\operatorname{lex}$-operation and a $\operatorname{pp}$-operation or (2)
$\mathscr{C}_{2}$ contains an $\operatorname{ll}$-operation. We may therefore
assume that $f_{1}=\operatorname{ll}_{3}$ since, otherwise, we can treat
$\psi$ as a weakly $1$-determined clause.

If one of the $a,b,c$ satisfies the literal $x\neq_{1}y$, then $f(a,b,c)$
satisfies the literal as well since $\theta_{1}(f)=f_{1}$ is injective. So
suppose that none of $a,b,c$ satisfies such literals. We show that $f(a,b,c)$
satisfies $\psi^{\prime}$. Since $f_{2}\in\mathscr{C}_{2}$, there is
$f_{2}^{\prime}\in\operatorname{Pol}(\mathfrak{D})$ such that
$\theta_{2}(f_{2}^{\prime})=f_{2}$. Since $f_{2}^{\prime}$ preserves $\phi$
and the relation $=_{1}$, the tuple $f_{2}^{\prime}(a,b,c)$ must satisfy the
$2$-determined clause $\psi^{\prime}$ and hence $f_{2}(a,b,c)$ satisfies
$\hat{\psi^{\prime}}$ by Lemma 21. Another application of Lemma 21 shows that
$f(a,b,c)$ satisfies $\psi^{\prime}$ as well.

Finally, we prove that $f$ is indeed a pwnu polymorphism of $\mathfrak{D}$. If
$e^{i}_{1},e^{i}_{2},e^{i}_{3}$ show that $f_{i}$ is a pwnu polymorphism of
$\mathfrak{D}_{i}$, then $e_{j}:=(e^{1}_{j},e^{2}_{j})$, for
$j\in\\{1,2,3\\}$, are the endomorphisms of $\mathfrak{D}$ that show that $f$
is a pwnu polymorphism of $\mathfrak{D}$.

Since
$\overline{\operatorname{Aut}(\mathbb{Q};<)}=\operatorname{End}(\mathbb{Q};<)$,
it follows from Lemma 20 that
$\overline{\operatorname{Aut}(\mathfrak{D})}=\operatorname{End}(\mathfrak{D})$
so Lemma 13 implies that the two cases in the statement are mutually
exclusive. ∎

###  4.6 Classification in the $n$-Dimensional Case

The approach in the previous section can be generalised to first-order
expansions of
$(\mathbb{Q};<)^{(n)}=(\mathbb{Q}^{n};<_{1},=_{1},\dots,<_{n},=_{n})$. From
now on and for the remainder of Section 4, the symbol $\mathfrak{D}$ denotes
such an expansion. We begin by generalising Definition 49.

######  Definition 60.

Let $S\subseteq\\{1,\dots,n\\}$ and $p\in\\{1,\dots,n\\}$. A clause is called
_$S$ -weakly $p$-determined_ if it is of the form

$\psi\vee\bigvee_{i\in\\{1,\dots,k\\}\;{\rm and}\;j_{i}\in
S}x_{i}\neq_{j_{i}}y_{i}$

where $\psi$ is $p$-determined and $k\geq 0$. A clause is called _weakly
$p$-determined_ if it is $\\{1,\dots,n\\}\setminus\\{p\\}$-weakly
$p$-determined (note that this is consistent with the notion of weakly
$p$-determined for $n=2$ from Definition 49).

Next, we connect conjunctions of $S$-weakly $p$-determined clauses with first-
order expansions of $({\mathbb{Q}};<)^{(n)}$ that admit certain polymorphisms.

######  Proposition 61.

Suppose that for every $p\in\\{1,\dots,n\\}$ there is an operation
$f\in\operatorname{Pol}(\mathfrak{D})$ such that $\theta_{p}(f)$ is an
$\operatorname{ll}$-operation or a $\operatorname{pp}$-operation. Then for
every relation $R$ of $\mathfrak{D}$, if $\phi$ is a first-order definition of
$R$ over $(\mathbb{Q}^{n};<_{1},=_{1},\dots,<_{n},=_{n})$ that is normal, then
$\phi$ is a conjunction of clauses each of which is weakly $i$-determined for
some $i\in\\{1,\dots,n\\}$.

###### Proof.

The proof is a generalisation of the proof of Proposition 50; the key step is
to use the generalisation of Corollary 44 which states that for
$i,j\in\\{1,\dots,n\\}$ and $f\in\operatorname{Pol}(\mathfrak{D})$ such that
$\theta_{i}(f)$ is an $\operatorname{ll}$\- or a $\operatorname{pp}$-operation
there is an operation
$g\in\operatorname{Pol}(\mathfrak{D};\leq_{1},\neq_{1},\dots,\leq_{n},\neq_{n})$
such that

  * •

$\theta_{i}(g)$ is dominated by the first argument (or even equal to
$\pi_{1}^{2}$ if $\theta_{i}(f)$ is a $\operatorname{pp}$-operation) and

  * •

$\theta_{j}(g)$ is dominated by the second.

To prove this, note first that we may without loss of generality assume that
$f$ preserves $\leq_{k}$ and $\neq_{k}$ for all $k$; for $k=i$ this follows
from the assumption and for $k\neq i$ we may repeatedly apply the
$n$-dimensional generalisation of Lemma 42 (as discussed immediately after
Lemma 40) to obtain an operation that preserves $\leq_{k}$ and $\neq_{k}$. By
applying Lemma 42 to canonise the operation in the $j$-th position and
subsequent application of the $n$-dimensional generalisation of Lemma 43 to
modify the $i$-th position, we can prove the statement analogously to the
proof of Corollary 44.

To prove the proposition, one can proceed as in the proof of Proposition 50;
the only difference is that the choice of the polymorphism $g$ depends on the
considered pair of literals, because it needs to have the domination property
in the right dimensions. In fact, the generalisation of that proof yields the
conclusion under the weaker assumption that for all but at most one
$p\in\\{1,\dots,n\\}$ there exists $f\in\operatorname{Pol}(\mathfrak{D})$ such
that $\theta_{p}(f)$ is an $\operatorname{ll}$-operation, a
$\operatorname{pp}$-operation, or the dual of such an operation. ∎

The following proposition introduces a new syntactic normal form and describes
its relationship with polymorphisms. It can be viewed as a generalisation of
Propositions 51-56.

######  Proposition 62.

Let $S\subseteq\\{1,\dots,n\\}$ be such that

  * •

for every $p\in S$ there exists $f_{p}\in\operatorname{Pol}(\mathfrak{D})$
such that $\theta_{p}(f_{p})$ is an $\operatorname{ll}$-operation, and

  * •

for every $p\in\\{1,\dots,n\\}\setminus S$ there exists
$f_{p}\in\operatorname{Pol}(\mathfrak{D})$ such that $\theta_{p}(f_{p})$ is a
$\operatorname{pp}$-operation, but there is no
$g\in\operatorname{Pol}(\mathfrak{D})$ such that $\theta_{p}(g)$ is a
$\operatorname{lex}$-operation.

Then, the following hold:

  1. 1.

every relation of $\mathfrak{D}$ can be defined by a conjunction of clauses
each of which is an $S$-weakly $p$-determined clause for some
$p\in\\{1,\dots,n\\}$,

  2. 2.

if $p\in\\{1,\dots,n\\}\setminus S$, then the $S$-weakly $p$-determined
clauses can be chosen to be of the form

$u_{1}\neq_{i_{1}}v_{1}\vee\cdots u_{m}\neq_{i_{m}}v_{m}\vee
y_{1}\neq_{p}x\vee\cdots\vee y_{k}\neq_{p}x\vee z_{1}\leq_{p}x\vee\cdots\vee
z_{l}\leq_{p}x,$ (6)

where $i_{1},\dots,i_{m}\in S$, and

  3. 3.

if $p\in S$, then the $S$-weakly $p$-determined clauses can be chosen to be
$\operatorname{ll}$-Horn clauses of the form

$x_{1}\neq_{i_{1}}y_{1}\vee\cdots\vee x_{m}\neq_{i_{m}}y_{m}\vee
z_{1}<_{p}z_{0}\vee\cdots\vee
z_{\ell}<_{p}z_{0}\vee(z_{0}=_{p}z_{1}=_{p}\cdots=_{p}z_{\ell})$

for $i_{1},\dots,i_{m}\in S$ (and where the last disjunct may not appear).

###### Proof.

Every relation of $\mathfrak{D}$ has a definition by a normal formula and, by
Proposition 61, it can be defined by a conjunction of clauses each of which is
weakly $i$-determined for some $i\in\\{1,\dots,n\\}$. Let $R$ be a relation of
$\mathfrak{D}$ and let $\phi$ be such a definition. We show step by step that
the statements in items $1-3$ hold true for $R$.

Proof of item 1. Let $\psi$ be a weakly $i$-determined clause of $\phi$ for
some $i\in\\{1,\dots,n\\}$. When $i\in S$ and $j\in\\{1,\dots,n\\}\setminus
S$, then we can proceed as in the proof of Proposition 51: we use the
generalised version of Corollary 44 described in detail in the previous proof
and we rule out the possibility that $\psi$ simultaneously contains a
$\\{<_{i},=_{i}\\}$-literal and a $\neq_{j}$-literal. Therefore, $\psi$ is an
$S$-weakly $i$-determined clause or an $S$-weakly $j$-determined clause in
this case.

If $i,j\in\\{1,\dots,n\\}\setminus S$ are distinct, then there is an operation
$g\in\operatorname{Pol}(\mathfrak{D};\leq_{1},\neq_{1},\dots,\leq_{n},\neq_{n})$
with $\theta_{i}(g)=\pi_{1}^{2}$ and $\theta_{j}(g)=\pi_{2}^{2}$. To see this,
we first assume that $g$ preserves $\leq_{k}$ and $\neq_{k}$ for all $k$ — if
this is not the case, then we repeatedly apply Lemma 42 in all but the $i$-th
dimension. The existence of $g$ can now be proved similarly as in the proof of
Proposition 55 (the proof uses the fact that there is no
$g\in\operatorname{Pol}(\mathfrak{D})$ such that $\theta_{i}(g)$ or
$\theta_{j}(g)$ is a $\operatorname{lex}$-operation). As in the proof of Lemma
22, $g$ can be used to prove that $\psi$ cannot contain a
$\\{<_{i},=_{i},\neq_{i}\\}$-literal and $\neq_{j}$-literal at the same time.
Hence, the clause $\psi$ is an $S$-weakly $i$-determined clause. It follows
that the normal formula $\phi$ is in fact a conjunction of clauses each of
which is $S$-weakly $p$-determined for some $p$.

Proof of item 2. We now prove that we may choose the clauses that are
$S$-weakly $p$-determined for $p\not\in S$ to have the syntactic form (6). We
will proceed analogously to the proof of Proposition 53. Let
$p\in\\{1,\dots,n\\}\setminus S$ and $\phi=\phi_{p}\wedge\phi_{0}$, where
$\phi_{p}$ is the conjunction of all $S$-weakly $p$-determined clauses of
$\phi$ and $\phi_{0}$ is the conjunction of the remaining clauses. Let
$\phi_{p}^{\prime}$ be the conjunction of all clauses of the form (6) that are
reduced and implied by $\phi$. We will show that
$\phi^{\prime}=\phi_{p}^{\prime}\wedge\phi_{0}$ implies $\phi$ and hence
defines $R$. Applying the same procedure for all $p\in\\{1,\dots,n\\}\setminus
S$ concludes the proof of item 2.

To see that $\phi^{\prime}$ implies $\phi$, we use the same orbit argument as
in the proof of Proposition 53: $\phi_{p}$ is equivalent to a conjunction of
$S$-weakly $p$-determined clauses of the form

$\chi\vee y_{1}\circ_{1}y_{2}\vee\cdots\vee y_{k}\circ_{k}y_{k+1},$

where $\chi=\bigvee_{j=1}^{m}u_{j}\neq_{i_{j}}v_{j}$, $i_{j}\in S$,
$j=1,\dots,m$, and $\circ_{1},\dots,\circ_{k}\in\\{\neq_{p},\geq_{p}\\}$. We
assume that these clauses are minimal in the same sense as in the proof of
Proposition 53. Let $\psi$ be such a clause of $\phi$. The argument in the
rest of the proof of Proposition 53 is not dependent on the indices $i_{j}$ in
the literals $u_{j}\neq_{i_{j}}v_{j}$ in $\chi$. Thus, it is applicable also
in this case and shows that $\psi$ is implied by $\phi^{\prime}$. This proves
that $\phi^{\prime}$ implies $\phi$ since $\psi$ was chosen arbitrarily.

Proof of item 3. By items 1 and 2, we may assume without loss of generality
that $\phi$ satisfies the following condition: for every
$p\in\\{1,\dots,n\\}\setminus S$, every $S$-weakly $p$-determined clause of
$\phi$ is of the form (6). Let $\phi_{1}$ be a conjunction of all $S$-weakly
$p$-determined clauses of $\phi$ where $p\in S$ and let $\phi_{2}$ be the
conjuction of the remaining clauses of $\phi$. We will now use Corollary 26
and the conjunction replacement operator $\operatorname{cr}(\cdot)$. We note
that $\phi_{1}$ is a conjunction of $S$-determined clauses and hence $\phi$ is
equivalent to a formula $\psi_{1}\wedge\phi_{2}$ where
$\psi_{1}=\operatorname{cr}(\phi,S,\phi_{1})$. Without loss of generality, we
may assume that $\psi_{1}$ is normal. By Proposition 61, $\psi_{1}$ is in fact
a conjunction of clauses each of which is weakly $p$-determined for some $p$
and hence $S$-weakly $p$-determined for some $p\in S$.

Recall the variable expansion operator $\operatorname{ve}(\cdot)$ that we
defined just before Proposition 56. Since for every $p\in S$, there is an
operation $f_{p}\in\operatorname{Pol}(\mathfrak{D})$ such that
$\theta_{p}(f_{p})$ is an $\operatorname{ll}$-operation and $\psi_{1}$ is
$S$-determined, it can be shown analogously to the claim in the proof of
Proposition 56 that $\operatorname{ve}(\psi_{1})$ is preserved by every
$\operatorname{ll}$-operation. By Theorem 38, $\operatorname{ve}(\psi_{1})$ is
equivalent to a conjunction of $\operatorname{ll}$-Horn clauses. Since the
formula $\psi_{1}\wedge\phi_{2}$ defines $R$, item 3 follows. ∎

Note that the formula produced by Proposition 62 is not necessarily normal.
Also note the difference between the proof for $n=2$ and general $n$: For
$n=2$, there are just three cases – $S$ is empty, $S=\\{p\\}$ for some $p$, or
$S=\\{1,2\\}$. If $S=\\{p\\}$, then $S$-determined clauses are $p$-determined.
If $S=\\{1,2\\}$, then the formula $\phi_{1}$ is equal to $\phi$ and thus
trivially preserved by $\operatorname{Pol}(\mathfrak{D})$. We continue with a
computational result where the proof is similar to the proof of Proposition
58.

######  Proposition 63.

Suppose that $\mathfrak{D}$ has a finite relational signature $\tau$ and for
each $p\in\\{1,\dots,n\\}$ there exists
$f_{p}\in\operatorname{Pol}(\mathfrak{D})$ such that $\theta_{p}(f_{p})$
equals $\operatorname{ll}_{3}$, $\min_{3}$, $\operatorname{mx}_{3}$, or
$\operatorname{mi}_{3}$. Then, $\operatorname{CSP}(\mathfrak{D})$ can be
solved in polynomial time.

###### Proof.

Without loss of generality, suppose that for every $p\in\\{1,\dots,n\\}$ such
that $\theta_{p}(\operatorname{Pol}(\mathfrak{D}))$ contains
$\operatorname{ll}_{3}$, the operation $f_{p}$ is chosen to be such that
$\theta_{p}(f_{p})=\operatorname{ll}_{3}$. Let $S\subseteq\\{1,\dots,n\\}$ be
the set of all such $p$. Moreover, we may assume that $\mathfrak{D}$ contains
relations $\neq_{i}$ for every $i\in S$. Otherwise we repeatedly apply Lemma
40 on the operations $f_{p}$, $p\in\\{1,\dots,n\\}$, and obtain polymorphisms
$f_{p}^{\prime}$ such that

  * •

$\theta_{i}(f_{p}^{\prime})$ is canonical over
$\operatorname{Aut}(\mathbb{Q};<)$ for every $i\neq p$ (and hence preserves
$\neq_{i}$ by Lemma 41),

  * •

$\theta_{p}(f_{p})$ equals $\operatorname{ll}_{3}$, $\min_{3}$,
$\operatorname{mx}$, or $\operatorname{mi}_{3}$ (and hence preserves
$\neq_{p}$ whenever $p\in S$).

Note that $\theta_{p}(\operatorname{Pol}(\mathfrak{D}))$ contains a
$\operatorname{pp}$-operation for every $p\in\\{1,\dots,n\\}\setminus S$ (by
Proposition 17 and Proposition 32), but it does not contain a
$\operatorname{lex}$-operation (by Theorem 38). By Theorem 38,
$\theta_{p}(\operatorname{Pol}(\mathfrak{D}))$ contains a
$\operatorname{ll}$-operation for $p\in S$. Let $\mathfrak{A}$ be an instance
of $\operatorname{CSP}(\mathfrak{D})$. For every $R\in\tau$ of arity $k$ and
$\bar{a}=(a_{1},\dots,a_{k})\in R^{\mathfrak{A}}$, let $\phi_{R,\bar{a}}$ be
the first-order definition of $R$ in the structure
$(\mathbb{Q}^{n};<_{1},=_{1},\dots,<_{n},=_{n})$ using the elements
$a_{1},\dots,a_{k}$ as the free variables. We then may assume that
$\phi_{R,\bar{a}}$ is of the form as described in Proposition 62.

input : an instance $\mathfrak{A}$ of $\operatorname{CSP}(\mathfrak{D})$

$\Phi\coloneqq\\{\phi_{R,\bar{a}}\mid R\in\tau,\bar{a}\in R^{\mathfrak{A}}\\}$

foreach  _$\phi\in\Phi$_ do

write $\phi$ as $\bigwedge_{p\in\\{1,\dots,n\\}\setminus
S}{\phi_{p}}\wedge\phi_{S}$, where $\phi_{p}$ is a conjunction of $S$-weakly
$p$-determined clauses and $\phi_{S}$ is a conjunction of $S$-determined
$\operatorname{ll}$-Horn clauses

$\Psi_{S}\coloneqq\\{\operatorname{ve}(\phi_{S})\mid\phi\in\Phi\\}$

// $\Psi_{S}$ contains conjunctions of $\operatorname{ll}$-Horn clauses over
$(\mathbb{Q},<)$ and its

// satisfiability can be checked in polynomial time by Theorems 29 and 38.

if  _$\Psi_{S}$ is not satisfiable_ then

reject

let $E$ denote the equality set corresponding to $\Psi_{S}$

foreach  _$\phi\in\Phi$_ do

write $\operatorname{cm}(\phi,E)$ as $\bigwedge_{p\in\\{1,\dots,n\\}\setminus
S}{\phi_{p}^{\prime}}\wedge\phi_{S}\wedge\phi_{S}^{\prime}$, where
$\phi_{p}^{\prime}$ is the conjunction of $p$-determined clauses resulting
from $\phi_{p}$ and $\phi_{S}^{\prime}$ is a conjunction of the added
conjuncts

$\Phi^{\prime}\coloneqq\\{\operatorname{cm}(\phi,E)\mid\phi\in\Phi\\}$

foreach  _$p\in\\{1,\dots,n\\}\setminus S$_ do

// Every $\phi^{\prime}\in\Phi^{\prime}$ defines a relation that is
primitively positively

// definable over $\mathfrak{D}$.

$\Psi_{p}\coloneqq\\{\hat{\psi_{p}}\mid\phi^{\prime}\in\Phi^{\prime},\psi_{p}=\operatorname{cr}(\phi^{\prime},\\{p\\},\phi_{p}^{\prime})\\}$

// $\Psi_{p}$ is preserved by $\min_{3}$, $\operatorname{mx}_{3}$, or
$\operatorname{mi}_{3}$ and its satisfiability

// can be checked in polynomial time by Theorems 28 and 29.

if  _$\Psi_{p}$ is not satisfiable_ then

reject

accept

Algorithm 1 $\operatorname{CSP}(\mathfrak{D})$

In Algorithm 1 we present the algorithm for deciding whether a given instance
$\mathfrak{A}$ of $\operatorname{CSP}(\mathfrak{D})$ has a homomorphism to
$\mathfrak{D}$. The algorithm uses the same ideas as are used in the proof of
Proposition 58. In particular, we can show by similar arguments that the sets
$\Phi$, $\Psi_{S}$, $\Phi^{\prime}$ and $\Psi_{p}$,
$p\in\\{1,\dots,n\\}\setminus S$, can be computed in polynomial time. Finally,
the set $E$ can be computed in polynomial time (as was pointed out after
Proposition 57) so the whole algorithm runs in polynomial time.

It is clear that if the algorithm rejects, then there is no homomorphism from
$\mathfrak{A}$ to $\mathfrak{D}$. In case that the algorithm accepts, the
existence of a homomorphism from $\mathfrak{A}$ to $\mathfrak{D}$ can be
proved in a similar fashion as in the proof of Proposition 58. ∎

We are now in the position of proving the main result of this section.

######  Theorem 64.

Exactly one of the following two cases applies.

  * •

For each $p\in\\{1,\dots,n\\}$ we have that
$\theta_{p}(\operatorname{Pol}(\mathfrak{D}))$ contains $\min_{3}$,
$\operatorname{mx}_{3}$, $\operatorname{mi}_{3}$, or $\operatorname{ll}_{3}$,
or one of their duals. In this case, $\mathfrak{D}$ has a pwnu polymorphism.
If $\mathfrak{D}$ has a finite relational signature, then
$\operatorname{CSP}(\mathfrak{D})$ is in P.

  * •

$\operatorname{Pol}(\mathfrak{D})$ has a uniformly continuous minor-preserving
map to $\operatorname{Pol}(K_{3})$. In this case $\mathfrak{D}$ has a finite-
signature reduct whose $\operatorname{CSP}$ is NP-complete.

###### Proof.

For $p\in\\{1,\dots,n\\}$, define
${\mathscr{C}}_{p}\coloneqq\theta_{p}(\operatorname{Pol}(\mathfrak{D}))$. If
${\mathscr{C}}_{p}$, for some $p\in\\{1,\dots,n\\}$, has a uniformly
continuous minor-preserving map from ${\mathscr{C}}_{p}$ to
$\operatorname{Pol}(K_{3})$, then by composing uniformly continuous minor-
preserving maps there is also a uniformly continuous minor-preserving map from
$\operatorname{Pol}(\mathfrak{D})$ to $\operatorname{Pol}(K_{3})$. This
implies that $\mathfrak{D}$ has a finite-signature reduct whose
$\operatorname{CSP}$ is NP-hard by Corollary 12.

Otherwise, for every $p\in\\{1,\dots,n\\}$ the clone $\mathscr{C}_{p}$ does
not have a uniformly continuous minor-preserving map to
$\operatorname{Pol}(K_{3})$. Since ${\mathscr{C}}_{p}$ is a closed clone (by
Proposition 17) that contains $\operatorname{Aut}({\mathbb{Q}};<)$ and
preserves $<$, there exists a first-order expansion $\mathfrak{D}_{p}$ of
$\operatorname{Aut}({\mathbb{Q}};<)$ such that
$\operatorname{Pol}(\mathfrak{D}_{p})={\mathscr{C}}_{p}$. We may therefore
apply Theorem 29 and conclude that for every $p\in\\{1,\dots,n\\}$ the clone
${\mathscr{C}}_{p}$ contains an operation $f_{p}$ which equals $\min_{3}$,
$\operatorname{mx}_{3}$, $\operatorname{mi}_{3}$, or $\operatorname{ll}_{3}$,
or the dual of one of these operations. By the version of Lemma 45 for
$n$-fold algebraic products, we may assume without loss of generality that
$f_{p}\in\\{\min_{3},\operatorname{mx}_{3},\operatorname{mi}_{3},\operatorname{ll}_{3}\\}$
for every $p\in\\{1,\dots,n\\}$. In case that $\mathfrak{D}$ has a finite
relational signature, the polynomial-time tractability of
$\operatorname{CSP}(\mathfrak{D})$ follows from Proposition 63.

We may assume that $f_{p}=\operatorname{ll}_{3}$ for every $p$ such that
$\mathscr{C}_{p}$ contains $\operatorname{ll}_{3}$. Let $f$ be the ternary
operation such that $\theta_{p}(f)$ equals $f_{p}$ for every
$p\in\\{1,\dots,n\\}$. We claim that $f$ preserves $\mathfrak{D}$. Let $\phi$
be a formula that defines a relation from $\mathfrak{D}$ and has the form as
described in Proposition 62 (the argument in the proof of Proposition 63
implies that the assumptions are satisfied). We show that $f$ preserves
$\phi$. Let $a,b,c$ be tuples that satisfy $\phi$ and let $\psi$ be a clause
of $\phi$. We see that there is a $p\in\\{1,\dots,n\\}$ such that $\psi$ is
$S$-weakly $p$-determined. As in the proof of Theorem 59, one can show that
$f(a,b,c)$ satisfies $\psi$. It follows that $f$ preserves $\phi$ and
$f\in\operatorname{Pol}(\mathfrak{D})$.

As in the case when $n=2$ (Theorem 59), we can show that $f$ is a pwnu
polymorphism, and hence it follows from Lemma 20 and Lemma 13 that the two
cases of the statement are mutually exclusive. ∎

###  4.7 Classification of Binary Relations

A relational signature is called _binary_ if all its relation symbols have
arity two, and a relational structure is binary if its signature is binary. If
$\mathfrak{D}$ is binary, then the results from the previous sections can be
substantially strengthened. Note that an $\omega$-categorical structure has
only finitely many distinct relations of arity at most two so we may assume
that binary structures have a finite signature.

######  Definition 65.

A formula is called an _Ord-Horn clause_ if it is of the form

$x_{1}\neq y_{1}\vee\cdots\vee x_{m}\neq y_{m}\vee z_{1}\;\circ\;z_{0}$

where $\circ\in\\{<,\leq,=\\}$, it is permitted that $m=0$, and the final
disjunct may be omitted. An _Ord-Horn formula_ is a conjunction of Ord-Horn
clauses.

Ord-Horn clauses are ll-Horn and a first-order formula over $(\mathbb{Q};<)$
is equivalent to an Ord-Horn formula if and only if it is preserved by an
$\operatorname{ll}$-operation and the dual of an $\operatorname{ll}$-operation
[BK10]. We say that a relation has an Ord-Horn definition if it can be defined
by an Ord-Horn formula. The polynomial-time tractability of
$\operatorname{CSP}(\mathfrak{B})$ if all relations of $\mathfrak{B}$ have an
Ord-Horn definition follows from Theorem 29 and Theorem 38, but this was first
shown by Nebel and Bürckert [NB95] using a very different approach.

######  Theorem 66.

Suppose that $\mathfrak{D}$ is binary. Then exactly one of the following two
cases applies.

  * •

Each relation in $\mathfrak{D}$, viewed as a relation of arity $2n$ over
${\mathbb{Q}}$, has an Ord-Horn definition. In this case, $\mathfrak{D}$ has a
pwnu polymorphism and $\operatorname{CSP}(\mathfrak{D})$ is in P.

  * •

$\operatorname{Pol}(\mathfrak{D})$ has a uniformly continuous minor-preserving
map to $\operatorname{Pol}(K_{3})$. In this case,
$\operatorname{CSP}(\mathfrak{D})$ is NP-complete.

###### Proof.

If the second item of the statement does not apply, then Theorem 64 implies
that $\mathfrak{D}$ has a pwnu polymorphism and for each $p\in\\{1,\dots,n\\}$
we have that $\theta_{p}(\operatorname{Pol}(\mathfrak{D}))$ contains
$\min_{3}$, $\operatorname{mx}_{3}$, $\operatorname{mi}_{3}$, or
$\operatorname{ll}_{3}$, or one of their duals. By Lemma 45 we may focus on
the situation that $\theta_{p}(\operatorname{Pol}(\mathfrak{D}))$ contains
$\min_{3}$, $\operatorname{mx}_{3}$, $\operatorname{mi}_{3}$, or
$\operatorname{ll}_{3}$ (note that the dual of a relation with an Ord-Horn
definition has an Ord-Horn definition as well). Then Proposition 32 and
Theorem 38 imply that the assumptions of Proposition 61 hold, and therefore
every relation of $\mathfrak{D}$ can be defined by a normal conjunction of
clauses each of which is weakly $s$-determined for some $s\in\\{1,\dots,n\\}$.
If such a clause contains two disjuncts of the form $x<_{i}y$ and $y<_{i}x$,
then replace the disjuncts by $x\neq_{i}y$. If such a clause contains two
disjuncts of the form $x=_{i}y$ and $x\neq_{i}y$, then remove the clause
(since it is always true). If such a clause contains two disjuncts of the form
$x<_{i}y$ and $x=_{i}y$, then replace the disjuncts by $x\leq_{i}y$. Since the
relations of $\mathfrak{D}$ are binary, the resulting formula is Ord-Horn. The
result follows since we know that the satisfiability of Ord-Horn formulas can
be decided in polynomial time. Lemma 13 implies that the two items cannot hold
simultaneously. ∎

The reader should note that the Ord-Horn fragment does not have a
characterisation in terms of equations satisfied by the polymorphism clone
[BPR20, Theorem 7.2].

##  5 Complexity Classification Transfer

Assume that ${\cal C}$ and ${\cal D}$ are classes of structures and that the
complexity of CSP$(\mathfrak{D})$ is known for every $\mathfrak{D}\in{\cal
D}$. A complexity classification transfer is a process that systematically
uses this information for inferring the complexity of CSP$(\mathfrak{C})$ for
every $\mathfrak{C}\in{\cal C}$. The particular method that we will use
originally appeared in [Bod21]. Combined with our classification for first-
order expansions of $(\mathbb{Q};<)^{(n)}$, this method allows us to derive
several new dichotomy results in Section 6.

Let $\mathfrak{C}$ and $\mathfrak{D}$ denote relational structures. Two
interpretations $I$ and $J$ of $\mathfrak{C}$ in $\mathfrak{D}$ are called
_primitively positively homotopic_ 111We follow the terminology from [AZ86].
(pp-homotopic) if the relation
$\\{(\bar{x},\bar{y})\;|\;I(\bar{x})=J(\bar{y})\\}$ is primitively positively
definable in $\mathfrak{D}$. The _identity interpretation_ of a
$\tau$-structure $\mathfrak{C}$ is the identity map on $C$, which is clearly a
primitive positive interpretation. We write $I_{1}\circ I_{2}$ for the natural
composition of two interpretations $I_{1}$ and $I_{2}$.

######  Definition 67.

Two structures $\mathfrak{C}$ and $\mathfrak{D}$ with a (primitive positive)
interpretation $I$ of $\mathfrak{C}$ in $\mathfrak{D}$ and a (primitive
positive) interpretation $J$ of $\mathfrak{D}$ in $\mathfrak{C}$ are called
_mutually (primitively positively) interpretable_. They are called
_(primitively positively) bi-interpretable_ if additionally $I\circ J$ and
$J\circ I$ are pp-homotopic to the identity interpretation.

Note that structures that are (primitively positively) bi-definable are in
particular bi-interpretable (via 1-dimensional interpretations).

######  Example 68.

The structure $({\mathbb{Q}};<)$ and the structure $({\mathbb{I}};{\sf m})$
from Example 7 are primitively positive bi-interpretable (Example 3.3.3 in
[Bod21]): the identity map $I$ on $\mathbb{I}$ is a 2-dimensional primitive
positive interpretation of $({\mathbb{I}};{\sf m})$ in $(\mathbb{Q};<)$, and
the projection $J\colon{\mathbb{I}}\to{\mathbb{Q}}$ to the first coordinate is
a 1-dimensional interpretation of $(\mathbb{Q};<)$ in $({\mathbb{I}};{\sf
m})$. The proof that the two interpretations provide a bi-interpretation
appears in the proof of Theorem 77 in a slightly more general setting.

first-order expansions of
$\mathfrak{D}$$\mathfrak{D}$$\mathfrak{D}^{\prime}$first-order expansions of
$\mathfrak{C}$$\mathfrak{C}$$\mathfrak{C}^{\prime}$$I$$J$$I$$J$$J\circ
I{=_{\rm pp}}$ id Figure 1: Visualisation of Theorem 69. We use the symbol
$=_{\rm pp}$ to denote that two interpretations are pp-homotopic.

The proof of Theorem 3.4.1 in [Bod21] shows the following stronger statement.

######  Theorem 69.

Suppose $\mathfrak{D}$ has a primitive positive interpretation $I$ in
$\mathfrak{C}$, and $\mathfrak{C}$ has a primitive positive interpretation $J$
in $\mathfrak{D}$ such that $J\circ I$ is pp-homotopic to the identity
interpretation of $\mathfrak{C}$. Then for every first-order expansion
$\mathfrak{C}^{\prime}$ of $\mathfrak{C}$ there is a first-order expansion
$\mathfrak{D}^{\prime}$ of $\mathfrak{D}$ such that $I$ is a primitive
positive interpretation of $\mathfrak{D}^{\prime}$ in $\mathfrak{C}^{\prime}$
and $J$ is a primitive positive interpretation of $\mathfrak{C}^{\prime}$ in
$\mathfrak{D}^{\prime}$. The theorem is described in Figure 1.

In particular, if $\mathfrak{C}$, $\mathfrak{D}$, $\mathfrak{C}^{\prime}$ and
$\mathfrak{D}^{\prime}$ are as in Theorem 69, and $\mathfrak{C}^{\prime}$ or
$\mathfrak{D}^{\prime}$ has a finite relational signature (and hence we may
assume that both have a finite signature), then
$\operatorname{CSP}(\mathfrak{C}^{\prime})$ and
$\operatorname{CSP}(\mathfrak{D}^{\prime})$ have the same computational
complexity (up to polynomial-time reductions) by Proposition 5. Now, let
${\cal C}$ and ${\cal D}$ denote the sets of first-order expansions of
$\mathfrak{C}$ and $\mathfrak{D}$, respectively, and assume that the
complexity of CSP$(\mathfrak{D})$ is known for every $\mathfrak{D}\in{\cal
D}$. It follows that we can deduce the complexity of CSP$(\mathfrak{C})$ for
every $\mathfrak{C}\in{\cal C}$.

##  6 Applications

This section demonstrates that our dichotomy result for first-order expansions
of the structure $({\mathbb{Q}}^{n};<_{1},=_{1},\dots,<_{n},=_{n})$ from
Section 4.6 can be combined with the complexity classification transfer result
from Section 5 to obtain surprisingly strong new classification results. We
obtain full classifications for the complexity of the CSP for first-order
expansions of several interesting structures; an overview can be found in
Table 2. Our results have stronger formulations when specialised to binary
languages; this yields simple new proofs of known results (Sections 6.1 and
6.2.1) and solves long-standing open problems from the field of temporal and
spatial reasoning (Sections 6.1 and 6.3). For the basic structures in Table 2,
our results show that the CSP for a first-order expansion $\mathfrak{B}$ is
polynomial-time solvable if and only if each relation in $\mathfrak{B}$ can be
defined via an Ord-Horn formula.

Formalism |  $({\mathbb{Q}}^{n};<_{1},=_{1},\dots,<_{n},=_{n})$ classification | Classification transfer
---|---|---
Cardinal Direction Calculus | for $n=2$ | not used
Generalized CDC | for general $n$ | not used
Interval Algebra | not used | used
Interval Algebra above $\\{\hbox{\sf s},\hbox{\sf f}\\}$ | for $n=2$ | used
Rectangle Algebra | for $n=2$ | used
$n$-dimensional Block Algebra | for general $n$ | used
Table 2: Overview of results and methods used for studying first-order
expansions of the basic relations (unless otherwise stated).

###  6.1 Cardinal Direction Calculus

The Cardinal Direction Calculus (CDC) [Lig98b] is a formalism where the basic
objects are the points in the plane, i.e., the domain is ${\mathbb{Q}}^{2}$.
The basic relations correspond to eight cardinal directions (North, East,
South, West and four intermediate ones) together with the equality relation.
The basic relations can be viewed as pairs $(R^{1},R^{2})$ for all choices of
$R^{1},R^{2}\in\\{<,=,>\\}$, where each relation applies to the corresponding
coordinate. The connection between cardinal directions and pairs
$(R^{1},R^{2})$ is described in Table 3. Let $\mathfrak{C}$ denote the
structure containing the basic relations of CDC. The classical formulation of
CDC contains all binary relations that are unions of relations in
$\mathfrak{C}$. In the sequel, we will additionally be interested in the
richer set of relations of arbitrary arity that are first-order definable in
$\mathfrak{C}$.

= | N | E | S | W | NE | SE | SW | NW
---|---|---|---|---|---|---|---|---
$(=,=)$ | $(=,>)$ | $(>,=)$ | $(=,<)$ | $(<,=)$ | $(>,>)$ | $(>,<)$ | $(<,<)$ | $(<,>)$
Table 3: The basic relations of Cardinal Direction Calculus

######  Theorem 70.

Let $\mathfrak{B}$ be a first-order expansion of $\mathfrak{C}$. Then exactly
one of the following two cases applies.

  * •

Each of $\theta_{1}(\operatorname{Pol}(\mathfrak{B}))$ and
$\theta_{2}(\operatorname{Pol}(\mathfrak{B}))$ contains
$\operatorname{mi}_{3}$, $\min_{3}$, $\operatorname{mx}_{3}$, or
$\operatorname{ll}_{3}$, or one of their duals. In this case,
$\operatorname{Pol}(\mathfrak{B})$ has a pwnu polymorphism. If the signature
of $\mathfrak{B}$ is finite, then $\operatorname{CSP}(\mathfrak{B})$ is in P.

  * •

$\operatorname{Pol}(\mathfrak{B})$ has a uniformly continuous minor-preserving
map to $\operatorname{Pol}(K_{3})$ and $\mathfrak{B}$ has a finite-signature
reduct whose CSP is NP-complete.

###### Proof.

Clearly, every relation in $\mathfrak{B}$ is first-order definable in
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$. Moreover, the relations in
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$ are primitively positively
definable in $\mathfrak{C}$:

  * •

$x<_{1}y$ is defined by $\exists z\big{(}x({\rm SW})z\wedge z({\rm
NW})y\big{)}$,

  * •

$x=_{1}y$ is defined by $\exists z\big{(}x({\rm S})z\wedge z({\rm
N})y\big{)}$, and

  * •

the relations $<_{2}$ and $=_{2}$ can be defined analogously.

Thus, the result follows immediately from Theorem 59 because every first-order
expansion of $\mathfrak{C}$ can be viewed as a first-order expansion of
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$. ∎

A slightly weaker version of the following result has been proved by Ligozat
[Lig98b] using a fundamentally different approach.

######  Corollary 71.

Let $\mathfrak{B}$ be a binary first-order expansion of ${\mathfrak{C}}$. Then
exactly one of the following cases applies.

  * •

Each relation in $\mathfrak{B}$, viewed as a relation of arity four over
${\mathbb{Q}}$, has an Ord-Horn definition. In this case, $\mathfrak{B}$ has a
pwnu polymorphism and $\operatorname{CSP}(\mathfrak{B})$ is in P.

  * •

$\operatorname{Pol}(\mathfrak{B})$ has a uniformly continuous minor-preserving
map to $\operatorname{Pol}(K_{3})$ and $\operatorname{CSP}(\mathfrak{B})$ is
NP-complete.

###### Proof.

Immediate consequence of Theorem 66. ∎

Ligozat [Lig01] and Balbiani et al. [BC02] discuss the natural generalisation
of CDC to the domain ${\mathbb{Q}}^{n}$: let CDCn denote this generalisation.
Balbiani et al. [BC02, Section 7] claim that a particular set of relations
(referred to as strongly preconvex) is a maximal tractable subclass in CDC3
that contains all basic relations, and they state that they have not been able
to generalise this result to higher dimensions. Theorem 70 and Corollary 71
can immediately be generalised to this setting by using our results for
$(\mathbb{Q};<)^{(n)}$. We conclude that the Ord-Horn class is the unique
maximal tractable subclass of CDCn ($n\geq 2$) that contains all basic
relations.

###  6.2 Allen’s Interval Algebra

We have already introduced Allen’s Interval Algebra in Example 7 to illustrate
interpretations. The complexity of all binary reducts of Allen’s Interval
Algebra have been classified in [KJJ03]. However, little is known about the
complexity of the CSP for first-order expansions of reducts of Allen’s
Interval Algebra. In this section we obtain classification results for first-
order expansions of some reducts of Allen’s Interval Algebra. For reducts of
Allen’s Interval Algebra that contain ${\sf m}$ this is an immediate
consequence of the transfer result from Section 5 (Section 6.2.1). For the
first-order expansions of the structure that just contains the relations ${\sf
s}$ and ${\sf f}$ (Section 6.2.2), we combine classification transfer with our
classification for the first-order expansions of
$({\mathbb{Q}};<_{1},=_{1},<_{2},=_{2})$ from Section 4.5.

####  6.2.1 First-order Expansions of $\\{{\sf m}\\}$

The following is a more explicit version of Theorem 3.4.3 in [Bod21] (which
only states that the CSP of a first-order expansions of
$({\mathbb{I}};\hbox{\sf m})$ is polynomial-time solvable or NP-complete).

######  Theorem 72.

Let $\mathfrak{B}$ be a first-order expansion of $({\mathbb{I}};\hbox{\sf
m})$. Then exactly one of the following cases applies.

  * •

The identity map on $\mathbb{I}$ is a 2-dimensional primitive positive
interpretation of $\mathfrak{B}$ in $\mathfrak{U}$, $\mathfrak{X}$,
$\mathfrak{I}$, or $\mathfrak{L}$. In this case, $\mathfrak{B}$ has a pwnu
polymorphism, and if $\mathfrak{B}$ has a finite signature then
$\operatorname{CSP}(\mathfrak{B})$ is polynomial-time solvable.

  * •

$\operatorname{Pol}(\mathfrak{B})$ has a uniformly continuous minor-preserving
map to $\operatorname{Pol}(K_{3})$ (and $\mathfrak{B}$ has a finite-signature
reduct whose CSP is NP-complete).

###### Proof.

From Example 68 we know that $({\mathbb{I}};\hbox{\sf m})$ and
$({\mathbb{Q}};<)$ are primitively positively bi-interpretable via
interpretations $I$ and $J$ of dimension 2 and 1, respectively, where $I$ is
the identity map on ${\mathbb{I}}$. Theorem 69 implies that there exists a
first-order expansion $\mathfrak{C}$ of $({\mathbb{Q}};<)$ such that $I$ is a
primitive positive interpretation of $\mathfrak{B}$ in $\mathfrak{C}$ and $J$
is a primitive positive interpretation of $\mathfrak{C}$ in $\mathfrak{B}$.

If $\mathfrak{C}$ has a primitive positive interpretation in $\mathfrak{U}$,
$\mathfrak{X}$, $\mathfrak{I}$, $\mathfrak{L}$, then $\mathfrak{B}$ has a
primitive positive interpretation in one of those structures. Since each of
$\mathfrak{U}$, $\mathfrak{X}$, $\mathfrak{I}$, and $\mathfrak{L}$ has a pwnu
polymorphism (Theorem 28) and since the existence of pwnu polymorphisms is
preserved by primitive positive interpretations (as was discussed in Section
2.3), the structure $\mathfrak{C}$ has a pwnu polymorphism. Furthermore, if
$\mathfrak{B}$ has a finite signature, then $\operatorname{CSP}(\mathfrak{B})$
has a polynomial-time reduction to the CSP of one of those structures by
Proposition 5. The polynomial-time tractability then follows from Theorem 28
and Theorem 29. Otherwise, Theorem 29 implies that
$\operatorname{Pol}(\mathfrak{C})$ has a uniformly continuous minor-preserving
map to $\operatorname{Pol}(K_{3})$. Since there is also a uniformly continuous
minor-preserving map from $\operatorname{Pol}(\mathfrak{B})$ to
$\operatorname{Pol}(\mathfrak{C})$ by Theorem 11, we can compose maps and
obtain a uniformly continous minor-preserving map from
$\operatorname{Pol}(\mathfrak{B})$ to $\operatorname{Pol}(K_{3})$. By
Corollary 12, $\mathfrak{B}$ has a finite-signature reduct whose CSP is NP-
complete.

The structure $(\mathbb{I};\hbox{\sf m})$ is homogeneous (see, e.g., [Bod21,
Example 5.5.5]). In order to apply Lemma 13 on the structure $\mathfrak{B}$,
we prove that
$\overline{\operatorname{Aut}(\mathfrak{B})}=\operatorname{End}(\mathfrak{B})$.
It is clear that
$\overline{\operatorname{Aut}(\mathfrak{B})}\subseteq\operatorname{End}(\mathfrak{B})$.
We prove the inverse inclusion. Every endomorphism of $(\mathbb{I};\hbox{\sf
m})$ is injective and preserves the complement of m since all basic relations
have a primitive positive definition in $(\mathbb{I};\hbox{\sf m})$ and every
pair of distinct intervals satisfies one of the basic relations (see Example
7). By the homogeneity of $(\mathbb{I};\hbox{\sf m})$, every restriction of
its endomorphism on a finite set extends to an automorphism so
$\operatorname{End}(\mathbb{I};\hbox{\sf
m})\subseteq\overline{\operatorname{Aut}(\mathbb{I};\hbox{\sf m})}$. Since
$\mathfrak{B}$ is a first-order expansion of $(\mathbb{I};\hbox{\sf m})$, we
get

$\operatorname{End}(\mathfrak{B})\subseteq\operatorname{End}(\mathbb{I};\hbox{\sf
m})\subseteq\overline{\operatorname{Aut}(\mathbb{I};\hbox{\sf
m})}=\overline{\operatorname{Aut}(\mathfrak{B})}.$

It follows from Lemma 13 that the two cases of the statement are mutually
exclusive. ∎

Nebel & Bürckert [NB95] proved (by a computer-generated proof) that if a
reduct $\mathfrak{B}$ of Allen’s Interval Algebra only contains relations that
have an Ord-Horn definition when considered as a relation of arity four over
${\mathbb{Q}}$, then $\operatorname{CSP}(\mathfrak{B})$ is in P. Otherwise,
and if it contains the relation $\sf m$, it has an NP-hard CSP. Later on,
Ligozat [Lig98a] presented a mathematical proof of this result. We can derive
a stronger variant of the results by Nebel & Bürckert and Ligozat as a
consequence of Theorem 72.

######  Theorem 73.

Let $\mathfrak{B}$ be a binary first-order expansion of
$({\mathbb{I}};\hbox{\sf m})$. Then exactly one of the following cases
applies.

  * •

Every relation of $\mathfrak{B}$, viewed as a relation of arity four over
${\mathbb{Q}}$, has an Ord-Horn definition. In this case, $\mathfrak{B}$ has a
pwnu polymorphism and $\operatorname{CSP}(\mathfrak{B})$ is in P.

  * •

$\operatorname{Pol}(\mathfrak{B})$ has a uniformly continuous minor-preserving
map to $\operatorname{Pol}(K_{3})$ and $\operatorname{CSP}(\mathfrak{B})$ is
NP-complete.

###### Proof.

If $\operatorname{Pol}(\mathfrak{B})$ has a uniformly continuous minor-
preserving map to $\operatorname{Pol}(K_{3})$, then the statement follows from
Corollary 12. Otherwise, Theorem 72 implies that $\mathfrak{B}$ has a pwnu
polymorphism and the identity map $I$ on ${\mathbb{I}}$ is a 2-dimensional
primitive positive interpretation in $\mathfrak{U}$, $\mathfrak{X}$,
$\mathfrak{I}$, or $\mathfrak{L}$. We claim that every relation $R$ of
$\mathfrak{B}$, considered as a relation of arity four over ${\mathbb{Q}}$,
has an Ord-Horn definition. Let $\phi(u_{1},u_{2},v_{1},v_{2})$ be the first-
order formula that defines $I^{-1}(R)$ over $({\mathbb{Q}};<)$. Note that if
$I(u_{1},u_{2})=u$ then $u_{1}<u_{2}$, and if $I(v_{1},v_{2})=v$ then
$v_{1}<v_{2}$, so $\phi$ implies $u_{1}<u_{2}\wedge v_{1}<v_{2}$.

We first consider the case that $\mathfrak{B}$ has a 2-dimensional primitive
positive interpretation in $\mathfrak{U}$, $\mathfrak{X}$, or $\mathfrak{I}$.
In this case, $\phi$ is preserved by a $\operatorname{pp}$-operation
(Proposition 32), and we may assume that $\phi$ has the syntactic form
described in Theorem 33. Since $\phi$ implies $u_{1}<u_{2}\wedge v_{1}<v_{2}$,
we may add these two conjuncts to $\phi$; note that the resulting formula is
still of the required form. We may additionally assume that $\phi$ is reduced,
because every formula obtained from $\phi$ by removing literals is again of
the required form. Each clause in $\phi$ has the form

$y_{1}\neq x\vee\cdots\vee y_{k}\neq x\vee z_{1}\leq x\vee\cdots\vee z_{l}\leq
x.$

We have to show that $l\leq 1$. If $u_{1}\in\\{z_{1},\dots,z_{l}\\}$ and
$u_{2}$ equals $x$ then the conjunct $u_{1}<u_{2}$ implies that the literal
$u_{1}\leq u_{2}$ is true in every satisfying assignment to $\phi$, which
means that the clause has no other literals by the assumption that $\phi$ is
reduced, and we are done. If $u_{1}$ equals $x$ and $u_{2}$ equals $z_{i}$,
for some $i\in\\{1,\dots,l\\}$, then the conjunct $u_{1}<u_{2}$ implies that
removing the literal $z_{i}\leq x$ would result in an equivalent formula, in
contradiction to the assumption that $\phi$ is reduced. If $u_{1}$ equals
$z_{i}$ and $u_{2}$ equals $z_{j}$ for some $i,j\in\\{1,\dots,l\\}$, then the
clause $u_{1}<u_{2}$ implies that the literal $z_{j}\leq x$ is redundant,
again in contradiction to the assumption that $\phi$ is reduced. We see that
if one of $u_{1},u_{2}$ is from $\\{z_{1},\dots,z_{l}\\}$, then the other
variable cannot be from $\\{x,z_{1},\dots,z_{l}\\}$. The same argument applies
to $v_{1}$ and $v_{2}$ and we conclude that $l\leq 1$.

Finally we consider the case that $\mathfrak{B}$ has a 2-dimensional primitive
positive interpretation in $\mathfrak{L}$. In this case, Theorem 38 implies
that every relation of $\mathfrak{B}$, considered as a relation of arity four
over ${\mathbb{Q}}$, has a definition $\phi(u_{1},u_{2},v_{1},v_{2})$ by a
conjunction of ll-Horn clauses

$x_{1}\neq y_{1}\vee\cdots\vee x_{m}\neq y_{m}\vee z_{1}<z_{0}\vee\cdots\vee
z_{l}<z_{0}\vee(z_{0}=z_{1}=\cdots=z_{l})$

(where the final disjunct might be missing). Again we may assume that $\phi$
contains the two clauses $u_{1}<u_{2}$ and $v_{1}<v_{2}$, and we may also
assume that $\phi$ is reduced in the sense that whenever we remove a literal
$z_{i}<z_{0}$ and remove $z_{i}$ from the final disjunct
$z_{0}=z_{1}=\cdots=z_{l}$, or if we remove the final disjunct entirely, we
obtain a formula which is not equivalent to $\phi$. It suffices to show that
this implies that $l\leq 1$. Again, we break into cases. If both $u_{1}$ and
$u_{2}$ are in $\\{z_{0},z_{1},\dots,z_{l}\\}$, then the final disjunct is
never satisfied, so we may assume that it is not present. If
$u_{1}\in\\{z_{1},\dots,z_{l}\\}$ and $u_{2}$ equals $z_{0}$, then the literal
$z_{i}<z_{0}$ would be true in every satisfying assignment to $\phi$, which
means that the clause has no other literals by the assumption that $\phi$ is
reduced, and we are done. If $u_{1},u_{2}\in\\{z_{1}\dots,z_{l}\\}$ we also
obtain a contradiction to the assumption that $\phi$ is reduced. If $u_{1}$
equals $z_{0}$ and $u_{2}$ equals $z_{i}$ for some $i\in\\{1,\dots,l\\}$, then
the literal $z_{i}<z_{0}$ would be false and can be removed, in contradiction
to $\phi$ being reduced. Again it follows that at most one of $u_{1}$ and
$u_{2}$ can appear in $\\{z_{0},\dots,z_{l}\\}$. Analogous reasoning for
$v_{1}$ and $v_{2}$ implies that $l\leq 1$.

As in the proof of Theorem 72, the disjointness of the two cases follows from
Lemma 13. ∎

####  6.2.2 First-order Expansions of $\\{{\sf s},{\sf f}\\}$

Despite the obvious difference between the domains ${\mathbb{I}}$ and
${\mathbb{Q}}^{2}$, there is a way to use our classification of the first-
order expansions of $({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$ to obtain
classification results for first-order expansions of $({\mathbb{I}};\hbox{\sf
s},\hbox{\sf f})$. Our starting point is the following definability result.

######  Lemma 74.

$({\mathbb{I}};\hbox{\sf s},\hbox{\sf f})$ and
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$ are primitively positively bi-
definable.

###### Proof.

Let $\mathfrak{B}$ be the structure with domain $B={\mathbb{Q}}^{2}$ and the
relations

$\displaystyle\hbox{\sf s}^{\mathfrak{B}}$ $\displaystyle\coloneqq\\{(a,b)\in
B^{2}\mid a=_{1}b\wedge a<_{2}b\\},$ $\displaystyle\hbox{\sf
f}^{\mathfrak{B}}$ $\displaystyle\coloneqq\\{(a,b)\in B^{2}\mid a=_{2}b\wedge
b<_{1}a\\}.$

Observation 1. The relation s can be defined by the same primitive positive
formula as the one above for $\hbox{\sf s}^{\mathfrak{B}}$ using the relations
$=_{1}$ and $<_{2}$ restricted to $\mathbb{I}$; the same is true for the
relations f and $\hbox{\sf f}^{\mathfrak{B}}$ using the relations $=_{2}$ and
$<_{1}$. $\hfill\diamond$

The relations in $({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$ can be
primitively positively defined in $\mathfrak{B}$ as follows.

$\displaystyle=_{1}$ $\displaystyle=\big{\\{}(a,b)\in B^{2}\mid\exists
c\big{(}c(\hbox{\sf s}^{\mathfrak{B}})a\wedge c(\hbox{\sf
s}^{\mathfrak{B}})b\big{)}\big{\\}},$ $\displaystyle=_{2}$
$\displaystyle=\big{\\{}(a,b)\in B^{2}\mid\exists c\big{(}c(\hbox{\sf
f}^{\mathfrak{B}})a\wedge c(\hbox{\sf f}^{\mathfrak{B}})b\big{)}\big{\\}},$
$\displaystyle<_{1}$ $\displaystyle=\big{\\{}(a,b)\in B^{2}\mid\exists
c,d\big{(}a=_{1}c\wedge d(\hbox{\sf f}^{\mathfrak{B}})c\wedge d(\hbox{\sf
s}^{\mathfrak{B}})b\big{)}\big{\\}},$ $\displaystyle<_{2}$
$\displaystyle=\big{\\{}(a,b)\in B^{2}\mid\exists c,d\big{(}b=_{2}c\wedge
d(\hbox{\sf s}^{\mathfrak{B}})c\wedge d(\hbox{\sf
f}^{\mathfrak{B}})a\big{)}\big{\\}}.$

Observation 2. The restrictions of the relations $<_{1},=_{1},<_{2},=_{2}$, on
the set $\mathbb{I}^{2}$ can be defined by the same primitive positive
formulas with $\hbox{\sf s}^{\mathfrak{B}}$ replaced by s and $\hbox{\sf
f}^{\mathfrak{B}}$ replaced by f. $\hfill\diamond$

Claim. The structures $\mathfrak{B}$ and $({\mathbb{I}};\hbox{\sf s},\hbox{\sf
f})$ are isomorphic.

We prove the statement by a back-and-forth argument. Suppose that $i$ is an
isomorphism between a finite substructure $\mathfrak{A}$ of
$({\mathbb{I}};\hbox{\sf s},\hbox{\sf f})$ and a finite substructure
$\mathfrak{A}^{\prime}$ of $\mathfrak{B}$. The sets $A$ and $A^{\prime}$
denote (as usual) the domains of $\mathfrak{A}$ and $\mathfrak{A}^{\prime}$,
respectively. Let

$\displaystyle A_{1}$ $\displaystyle\coloneqq\\{p\in{\mathbb{Q}}\mid(p,q)\in
A\\}$ $\displaystyle A^{\prime}_{1}$
$\displaystyle\coloneqq\\{p\in{\mathbb{Q}}\mid(p,q)\in A^{\prime}\\}$
$\displaystyle A_{2}$ $\displaystyle\coloneqq\\{q\in{\mathbb{Q}}\mid(p,q)\in
A\\}$ $\displaystyle A^{\prime}_{2}$
$\displaystyle\coloneqq\\{q\in{\mathbb{Q}}\mid(p,q)\in A^{\prime}\\}.$

Define $i_{1}\colon A_{1}\to A_{1}^{\prime}$ by setting $i_{1}(p)=p^{\prime}$
if there exist $q,q^{\prime}\in{\mathbb{Q}}$ such that
$i(p,q)=(p^{\prime},q^{\prime})$. Similarly, define $i_{2}\colon A_{2}\to
A_{2}^{\prime}$ by setting $i_{2}(q)=q^{\prime}$ if there exist
$p,p^{\prime}\in{\mathbb{Q}}$ such that $i(p,q)=(p^{\prime},q^{\prime})$. By
Observation 1, the isomorphisms $i$ and $i^{-1}$ preserve the relations
$<_{1},=_{1},<_{2},=_{2}$. Therefore $i_{1}$ and $i_{2}$ and their inverses
are well-defined bijections and preserve $<$. By the homogeneity of
$({\mathbb{Q}};<)$, there exist automorphisms $\alpha_{1}$ and $\alpha_{2}$
that extend $i_{1}$ and $i_{2}$.

For going forth, let $(a,b)\in{\mathbb{I}}\setminus A$. Then $i$ is extended
by setting $i(a,b)\coloneqq(\alpha_{1}(a),\alpha_{2}(b))$. Since $\alpha_{1}$
and $\alpha_{2}$ preserve $<$, the extended map $i$ preserves the relations
$<_{1},=_{1},<_{2},=_{2}$. Observation 2 implies that $i$ is a homomorphism
between a substructure of $(\mathbb{I};\hbox{\sf s},\hbox{\sf f})$ and a
substructure of $\mathfrak{B}$. The operations $\alpha_{1}$ and $\alpha_{2}$
are automorphisms of $(\mathbb{Q};<)$, hence $i$ is injective and $i^{-1}$
preserves $<_{1},=_{1},<_{2},=_{2}$. Therefore, the extension of $i$ is an
isomorphism.

For going back, let $(a^{\prime},b^{\prime})\in{\mathbb{Q}}^{2}\setminus
A^{\prime}$. Then $i$ is extended by setting
$i(\alpha_{1}^{-1}(a^{\prime}),\alpha_{2}^{-1}(b^{\prime}))\coloneqq(a^{\prime},b^{\prime})$;
to prove that the extension is an isomorphism, we may argue similarly as in
the forth step. Alternating between going back and going forth, we may thus
construct an isomorphism between the two countable structures
$({\mathbb{I}};\hbox{\sf s},\hbox{\sf f})$ and $\mathfrak{B}$.
$\hfill\diamond$

The claim implies that $({\mathbb{I}};\hbox{\sf s},\hbox{\sf f})$ is
isomorphic to the structure $\mathfrak{B}$, which is primitively positive
interdefinable with $({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$, i.e.,
$({\mathbb{I}};\hbox{\sf s},\hbox{\sf f})$ and
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$ are primitively positively bi-
definable. ∎

With the aid of Lemma 74, we can now proceed in a way that is similar to the
proof of Theorem 72. Before we prove the main result in Theorem 76, we first
need to verify that $(\mathbb{I};\hbox{\sf s},\hbox{\sf f})$ is homogeneous.

######  Lemma 75.

The structure $(\mathbb{I};\hbox{\sf s},\hbox{\sf f})$ is homogeneous.

###### Proof.

Suppose that $i$ is an isomorphism between finite substructures $\mathfrak{A}$
and $\mathfrak{A}^{\prime}$ of $(\mathbb{I};\hbox{\sf s},\hbox{\sf f})$. We
show that $i$ can be extended to an automorphism of $(\mathbb{I};\hbox{\sf
s},\hbox{\sf f})$ by a back-and-forth argument. The argument is very similar
to the proof of the claim in Lemma 74, therefore we only sketch it. Let the
sets $A_{1}$ and $A_{2}$ be defined as in the proof of the claim. As we
already noted in the proof of Lemma 74, the restrictions of the relations
$<_{1},=_{1},<_{2},=_{2}$ on the set $\mathbb{I}^{2}$ are primitively
positively definable in $(\mathbb{I};\hbox{\sf s},\hbox{\sf f})$. Thus we may
define the $<$-preserving bijections $i_{j}:A_{j}\rightarrow A_{j}^{\prime}$,
$j=1,2$, as in the proof of the claim. By homogeneity of $(\mathbb{Q},<)$,
there exist automorphisms $\alpha_{1}$ and $\alpha_{2}$ of $(\mathbb{Q},<)$
that extend $i_{1}$ and $i_{2}$, respectively.

For going forth, let $(a,b)\in\mathbb{I}\setminus A$, then we extend $i$ by
setting $i(a,b)=(\alpha_{1}(a),\alpha_{2}(b))$. For going back, let
$(a^{\prime},b^{\prime})\in\mathbb{I}\setminus A^{\prime}$, then $i$ is
extended by
$i(\alpha_{1}^{-1}(a^{\prime}),\alpha_{2}^{-1}(b^{\prime}))=(a^{\prime},b^{\prime})$.
The same argument as in the proof of the claim in Lemma 74 implies that these
extensions are isomorphisms. Alternating between going back and forth, we
construct an automorphism of the countable structure $(\mathbb{I};\hbox{\sf
s},\hbox{\sf f})$ that extends $i$. It follows that $(\mathbb{I};\hbox{\sf
s},\hbox{\sf f})$ is homogeneous. ∎

######  Theorem 76.

Let $\mathfrak{D}$ be a first-order expansion of $({\mathbb{I}};\hbox{\sf
s},\hbox{\sf f})$. Then exactly one of the following cases applies.

  * •

$\mathfrak{D}$ has a pwnu polymorphism. If $\mathfrak{D}$ has a finite
relational signature, then $\operatorname{CSP}(\mathfrak{D})$ is in P.

  * •

$\operatorname{Pol}(\mathfrak{D})$ has a uniformly continuous minor-preserving
map to $\operatorname{Pol}(K_{3})$. In this case, $\mathfrak{D}$ has a finite-
signature reduct whose CSP is NP-complete.

###### Proof.

There is a first-order expansion $\mathfrak{C}$ of
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$ such that $\mathfrak{D}$ has a
primitive positive interpretation in $\mathfrak{C}$ and vice versa, by Lemma
74 together with Theorem 69. If $\operatorname{Pol}(\mathfrak{D})$ has a
uniformly continuous minor-preserving map to $\operatorname{Pol}(K_{3})$, then
$\mathfrak{D}$ has a finite-signature reduct whose $\operatorname{CSP}$ is NP-
complete by Corollary 12. Otherwise, since there is a uniformly continuous
minor-preserving map from $\operatorname{Pol}(\mathfrak{D})$ to
$\operatorname{Pol}(\mathfrak{C})$ by Theorem 11,
$\operatorname{Pol}(\mathfrak{C})$ does not have a uniformly continuous minor-
preserving map to $\operatorname{Pol}(K_{3})$ as well. By Theorem 59,
$\mathfrak{C}$ has a pwnu polymorphism and $\operatorname{CSP}(\mathfrak{C})$
is in P if $\mathfrak{C}$ has a finite signature. Since primitive positive
interpretations preserve the existence of pwnu polymorphisms, $\mathfrak{D}$
has a pwnu polymorphism as well. Moreover, if $\mathfrak{D}$ has a finite
signature, then $\mathfrak{C}$ can be assumed to have a finite signature and
$\operatorname{CSP}(\mathfrak{D})$ is in P by Proposition 5.

To see that the two cases in the statement are mutually exclusive, we use
Lemma 13. By Lemma 75, $(\mathbb{I};\hbox{\sf s},\hbox{\sf f})$ is
homogeneous. We prove that $\operatorname{End}(\mathbb{I};\hbox{\sf
s},\hbox{\sf f})\subseteq\overline{\operatorname{Aut}(\mathbb{I};\hbox{\sf
s},\hbox{\sf f})}$. Note that every pair of intervals satisfies exactly one of
the following relations: $\hbox{\sf p}\cup\hbox{\sf m}\cup\hbox{\sf o}$,
$\hbox{\sf p${}^{\smallsmile}$}\cup\hbox{\sf m${}^{\smallsmile}$}\cup\hbox{\sf
o${}^{\smallsmile}$}$, d, d⌣, s, s⌣, f, f⌣, $\equiv$. The relations $\equiv$,
s, and f are trivially primitively positively definable in
$(\mathbb{I};\hbox{\sf s},\hbox{\sf f})$. Moreover, all the remaining
relations are primitively positively definable as well, since the relation
$\hbox{\sf p}\cup\hbox{\sf m}\cup\hbox{\sf o}$ has the definition

$\exists z(x(\hbox{\sf s})z\wedge y(\hbox{\sf f})z),$

the relation d has the definition

$\exists z(x(\hbox{\sf s})z\wedge z(\hbox{\sf f})y),$

and the remaining definitions are obtained by exchanging the roles of $x$ and
$y$ in the definitions of the relations s, f, $\hbox{\sf p}\cup\hbox{\sf
m}\cup\hbox{\sf o}$, and d. Since endomorphisms preserve primitively
positively definable relations, it follows that the endomorphisms of
$(\mathbb{I};\hbox{\sf s},\hbox{\sf f})$ are injective and preserve also the
complements of s and f. Therefore, a restriction of an endomorphism of
$(\mathbb{I};\hbox{\sf s},\hbox{\sf f})$ is an isomorphism and can be extended
to an automorphism by the homogeneity of $(\mathbb{I};\hbox{\sf s},\hbox{\sf
f})$. This implies that $\operatorname{End}(\mathbb{I};\hbox{\sf s},\hbox{\sf
f})\subseteq\overline{\operatorname{Aut}(\mathbb{I};\hbox{\sf s},\hbox{\sf
f})}$. Since $\mathfrak{D}$ is a first-order expansion of
$(\mathbb{I};\hbox{\sf s},\hbox{\sf f})$,

$\operatorname{End}(\mathfrak{D})\subseteq\operatorname{End}(\mathbb{I};\hbox{\sf
s},\hbox{\sf f})\subseteq\overline{\operatorname{Aut}(\mathbb{I};\hbox{\sf
s},\hbox{\sf f})}=\overline{\operatorname{Aut}(\mathfrak{D})}.$

Clearly,
$\overline{\operatorname{Aut}(\mathfrak{D})}\subseteq\operatorname{End}(\mathfrak{D})$,
which implies
$\overline{\operatorname{Aut}(\mathfrak{D})}=\operatorname{End}(\mathfrak{D})$.
By Lemma 13, the cases in the statement are mutually exclusive. ∎

We note that relations s and f are primitively positively definable in
$\\{\hbox{\sf m}\\}$ but m is not primitively positively definable in
$\\{\hbox{\sf s},\hbox{\sf f}\\}$, so Theorem 76 is incomparable to Theorem
72.

###  6.3 Block Algebra

We will now study the $n$-dimensional block algebra ($\mathfrak{BA}_{n}$) by
Balbiani et al. [BCdC02]. This formalism has become widespread since it can
capture directional information in spatial reasoning, something that the
classical RCC formalisms cannot. Let $n\geq 1$ be an integer. The
$n$-dimensional block algebra has the domain ${\mathbb{I}}^{n}$. For relations
$R^{1},\dots,R^{n}$ from the interval algebra, we write

$\\{((x_{1},\dots,x_{n}),(y_{1},\dots,y_{n}))\in({\mathbb{I}}^{n})^{2}\;|\;x_{i}(R^{i})y_{i},\;1\leq
i\leq n\\}.$

The structure $\mathfrak{BA}_{n}$ contains all such relations, and we say that
the relation $(R^{1}|R^{2}|\dots|R^{n})$ is basic if $R^{1},\dots,R^{n}$ are
basic relations in the interval algebra. We note that $\mathfrak{BA}_{1}$ is
the interval algebra and that $\mathfrak{BA}_{2}$ is often referred to as the
rectangle algebra (RA) [Gue89, MJ90].

We begin by studying first-order expansions of $({\mathbb{I}};{\sf
m})\boxtimes({\mathbb{I}};{\sf m})=({\mathbb{I}}^{2};{\sf m}_{1},=_{1},{\sf
m}_{2},=_{2})$. It is easy to see that the relation $=_{i}$ is primitively
positively definable by $\hbox{\sf m}_{i}$, hence it is equivalent to study
the first-order expansions of the structure $({\mathbb{I}}^{2};{\sf
m}_{1},{\sf m}_{2})$. Note that the relation ${\sf m}_{1}$ and ${\sf m}_{2}$
over ${\mathbb{I}}^{2}$ can be written as $({\sf m}|\top)$ and $(\top|{\sf
m})$ respectively in the terminology of the Block Algebra. Also note that
${\sf m}_{1}$ and ${\sf m}_{2}$ are primitively positively definable over the
basic relations of the rectangle algebra: for example, $\exists z(x({\sf
m}|{\sf p})z\wedge y(\equiv|{\sf p})z)$ is equivalent to $x({\sf m}|\top)y$.
The fact that every basic relation in the interval algebra has a primitive
positive definition over $({\mathbb{I}};{\sf m})$ [AH85] now immediately
implies that every RA relation has a primitive positive definition over
$({\mathbb{I}}^{2};\hbox{\sf m}_{1},\hbox{\sf m}_{2})$. Hence, the results
below imply a classification of the Rectangle Algebra above the basic
relations.

######  Theorem 77.

Let $\mathfrak{D}$ be a first-order expansion of the structure
$({\mathbb{I}}^{2};\hbox{\sf m}_{1},\hbox{\sf m}_{2})$. Then there exists a
first-order expansion $\mathfrak{C}$ of
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$ such that $\mathfrak{D}$ has a
2-dimensional primitive positive interpretation in $\mathfrak{C}$ and
$\mathfrak{C}$ has a 1-dimensional primitive positive interpretation in
$\mathfrak{D}$.

Furthermore, exactly one of the following two cases applies.

  * •

$\mathfrak{D}$ has a pwnu polymorphism. If the signature of $\mathfrak{D}$ is
finite, then $\operatorname{CSP}(\mathfrak{D})$ is in P.

  * •

There exists a uniformly continuous minor-preserving map from
$\operatorname{Pol}(\mathfrak{D})$ to $\operatorname{Pol}(K_{3})$ and
$\mathfrak{D}$ has a finite-signature reduct whose CSP is NP-complete.

###### Proof.

For the first part of the statement we apply Theorem 69; so it suffices to
prove that $({\mathbb{I}}^{2};\hbox{\sf m}_{1},\hbox{\sf m}_{2})$ and
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$ are primitively positively bi-
interpretable via interpretations of dimension 2 and 1, respectively. This is
basically the primitive positive bi-interpretation of $({\mathbb{I}};\hbox{\sf
m})$ and $({\mathbb{Q}};<)$ from Example 3.3.3 in [Bod21] performed in each
dimension separately.

  * •

There is a 2-dimensional interpretation $I$ of $({\mathbb{I}}^{2};\hbox{\sf
m}_{1},\hbox{\sf m}_{2})$ in $({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$
whose domain $U\subseteq(\mathbb{Q}^{2})^{2}$ has the primitive positive
definition $\delta(a,b)$ given by $a<_{1}b\wedge a<_{2}b$. The interpretation
$I\colon U\to{\mathbb{I}}^{2}$ is given by

$((a_{1},a_{2}),(b_{1},b_{2}))\mapsto((a_{1},b_{1}),(a_{2},b_{2})).$

The relation

$I^{-1}(\hbox{\sf m}_{i})=\\{((a,b),(c,d))\mid I(a,b)\>(\hbox{\sf
m}_{i})\>I(c,d)\\}\subseteq U^{2}$

has the primitive positive definition $b=_{i}c$ in
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$. The relation

$I^{-1}((\equiv|\equiv))=\\{((a,b),(c,d))\mid
I(a,b)\>(\equiv|\equiv)\>I(c,d)\\}\subseteq U^{2}$

has the primitive positive definition $a=_{1}c\wedge a=_{2}c\wedge
b=_{1}d\wedge b=_{2}d$ in $({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$.

  * •

There is a one-dimensional interpretation
$J:\mathbb{I}^{2}\rightarrow\mathbb{Q}^{2}$ of
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$ in $({\mathbb{I}}^{2};\hbox{\sf
m}_{1},\hbox{\sf m}_{2})$ given by

$((p_{1},p_{2}),(q_{1},q_{2}))\mapsto(p_{1},q_{1}).$

The relation

$J^{-1}(<_{i})=\\{(x,y)\mid J(x)<_{i}J(y)\\}\subseteq(\mathbb{I}^{2})^{2}$

has the primitive positive definition

$\exists u,v(u(\hbox{\sf m}_{i})x\wedge u(\hbox{\sf m}_{i})v\wedge v(\hbox{\sf
m}_{i})y)$

in $({\mathbb{I}}^{2};\hbox{\sf m}_{1},\hbox{\sf m}_{2})$. The relation
$J^{-1}(=_{i})$ has the primitive positive definition

$\phi_{i}(x,y)\coloneqq\exists u(u(\hbox{\sf m}_{i})x\wedge u(\hbox{\sf
m}_{i})y)$

in $({\mathbb{I}}^{2};\hbox{\sf m}_{1},\hbox{\sf m}_{2})$ so $J^{-1}(=)$ has
the definition $\phi_{1}(x,y)\wedge\phi_{2}(x,y)$.

  * •

$J\circ I$ is pp-homotopic to the identity interpretation: We have

$J(I(a,b))=c\text{ if and only if }a=c.$

  * •

$I\circ J$ is pp-homotopic to the identity interpretation: Note that the
formula $\phi_{i}((x^{1},x^{2}),(y^{1},y^{2}))$ defines the relation

$\\{((x^{1},x^{2}),(y^{1},y^{2}))\mid
x^{i}=_{1}y^{i}\\}\subseteq(\mathbb{I}^{2})^{2}$

in $({\mathbb{I}};\hbox{\sf m}_{i})$. If
$x=((x^{1}_{1},x^{1}_{2}),(x^{2}_{1},x^{2}_{2}))$ and
$y=((y^{1}_{1},y^{1}_{2}),(y^{2}_{1},y^{2}_{2}))$ are elements of
${\mathbb{I}}^{2}$, then

$I(J(x),J(y))=I((x^{1}_{1},x^{2}_{1}),(y^{1}_{1},y^{2}_{1}))=((x^{1}_{1},y^{1}_{1}),(x^{2}_{1},y^{2}_{1})).$

Therefore we have $I(J(x),J(y))\>(\equiv|\equiv)\>z$ if and only if

$\phi_{1}(x,z)\wedge z(\hbox{\sf m}_{1})y\wedge\phi_{2}(x,z)\wedge z(\hbox{\sf
m}_{2})y.$

This concludes the proof of the first statement.

To prove the second statement, suppose that there is no uniformly continuous
minor-preserving map from $\operatorname{Pol}(\mathfrak{D})$ to
$\operatorname{Pol}(K_{3})$—otherwise, we are done by Corollary 12. Since
there is a primitive positive interpretation of $\mathfrak{C}$ in
$\mathfrak{D}$, there is a uniformly continuous clone homomorphism from
$\operatorname{Pol}(\mathfrak{D})$ to $\operatorname{Pol}(\mathfrak{C})$ by
Lemma 10, and there cannot exist a uniformly continuous minor-preserving map
from $\operatorname{Pol}(\mathfrak{C})$ to $\operatorname{Pol}(K_{3})$. It now
follows from Theorem 59 that $\operatorname{Pol}(\mathfrak{C})$ has a pwnu
polymorphism and if $\mathfrak{C}$ has a finite relational signature then
$\operatorname{CSP}(\mathfrak{C})$ is in P. By the first statement, there is
also a primitive positive interpretation of $\mathfrak{D}$ in $\mathfrak{C}$.
Therefore, the polynomial-time tractability of
$\operatorname{CSP}(\mathfrak{D})$ in the finite signature case follows from
Lemma 9. Moreover, there is a clone homomorphism from
$\operatorname{Pol}(\mathfrak{C})$ to $\operatorname{Pol}(\mathfrak{D})$,
again by Lemma 10. Therefore, $\mathfrak{D}$ has a pwnu polymorphism as well.

Finally, we show that the two cases in the statement are mutually exclusive.
In the proof of Theorem 72, we noted that $(\mathbb{I};\hbox{\sf m})$ is
homogeneous and $\operatorname{End}(\mathbb{I};\hbox{\sf
m})\subseteq\overline{\operatorname{Aut}(\mathbb{I};\hbox{\sf m})}$ so we
conclude that $\operatorname{End}(\mathbb{I};\hbox{\sf
m})=\overline{\operatorname{Aut}(\mathbb{I};\hbox{\sf m})}$. Let
$\mathfrak{D}^{\prime}$ be a first-order expansion of $\mathfrak{D}$ by the
relations $=_{1}$ and $=_{2}$, then $\mathfrak{D}^{\prime}$ is a first-order
expansion of $(\mathbb{I};\hbox{\sf m})\boxtimes(\mathbb{I};\hbox{\sf m})$. By
Lemma 20,
$\overline{\operatorname{Aut}(\mathfrak{D}^{\prime})}=\operatorname{End}(\mathfrak{D}^{\prime})$.
Since $=_{1}$ and $=_{2}$ are primitively positively definable in
$\mathfrak{D}$, we obtain that
$\overline{\operatorname{Aut}(\mathfrak{D})}=\operatorname{End}(\mathfrak{D})$.
Since $\mathfrak{D}$ is a first-order reduct of the homogeneous structure
$(\mathbb{I};\hbox{\sf m})\boxtimes(\mathbb{I};\hbox{\sf m})$, the two cases
are mutually exclusive by Lemma 13. ∎

We now consider binary first-order expansions of $({\mathbb{I}}^{2};\hbox{\sf
m}_{1},\hbox{\sf m}_{2})$. The proof combines arguments from Theorem 73 and
Theorem 77.

######  Theorem 78.

Let $\mathfrak{B}$ be a binary first-order expansion of
$({\mathbb{I}}^{2};\hbox{\sf m}_{1},\hbox{\sf m}_{2})$. Then exactly one of
the following cases applies.

  * •

Every relation of $\mathfrak{B}$, viewed as a relation of arity $8$ over
${\mathbb{Q}}$, has an Ord-Horn definition. In this case, $\mathfrak{B}$ has a
pwnu polymorphism and $\operatorname{CSP}(\mathfrak{B})$ is in P.

  * •

$\operatorname{Pol}(\mathfrak{B})$ has a uniformly continuous minor-preserving
map to $\operatorname{Pol}(K_{3})$ and $\operatorname{CSP}(\mathfrak{B})$ is
NP-complete.

###### Proof.

Let $\mathfrak{B}^{\prime}$ be the first-order expansion of
$({\mathbb{Q}}^{2};<_{1},=_{1},<_{2},=_{2})$ such that $\mathfrak{B}$ has a
2-dimensional primitive positive interpretation $I$ in $\mathfrak{B}^{\prime}$
and $\mathfrak{B}^{\prime}$ has a 1-dimensional primitive positive
interpretation in $\mathfrak{B}$ which exists by Theorem 77. By Theorem 69,
$I$ may be taken to be the same interpretation $I\colon U\to{\mathbb{I}}^{2}$
as in the proof of Theorem 77, where $U=\\{(a,b)\in\mathbb{Q}^{2}\mid
a<_{1}b\wedge a<_{2}b\\}$ and

$I:((a_{1},a_{2}),(b_{1},b_{2}))\mapsto((a_{1},b_{1}),(a_{2},b_{2})).$

If $\operatorname{Pol}(\mathfrak{B})$ has a uniformly continuous minor-
preserving map to $\operatorname{Pol}(K_{3})$, then
$\operatorname{CSP}(\mathfrak{B})$ is NP-hard by Corollary 12. Otherwise, it
follows from Lemma 10 that $\operatorname{Pol}(\mathfrak{B}^{\prime})$ does
not have a uniformly continous minor-preserving map to
$\operatorname{Pol}(K_{3})$ and Theorem 59 implies that for each
$i\in\\{1,2\\}$ there exists
$f_{i}\in\operatorname{Pol}(\mathfrak{B}^{\prime})$ such that
$\theta_{i}(f_{i})$ equals $\min_{3}$, $\operatorname{mx}_{3}$,
$\operatorname{mi}_{3}$, $\operatorname{ll}_{3}$, or one of their duals and
that $\operatorname{CSP}(\mathfrak{B}^{\prime})$ is in P. By Proposition 5,
$\operatorname{CSP}(\mathfrak{B})$ is in P, too. In this case, $\mathfrak{B}$
has a pwnu polymorphism by Theorem 77; the theorem also implies that the two
cases in the statement are mutually exclusive.

It remains to show that every (binary) relation of $\mathfrak{B}$, considered
as a relation of arity $8$ over ${\mathbb{Q}}$, has an Ord-Horn definition.
Let $R$ be a relation of $\mathfrak{B}$. Observe that it is sufficient to show
that the $4$-ary relation $I^{-1}(R)$ has a definition $\phi$ that is a
conjunction of clauses of the form

$x_{1}\neq_{i_{1}}y_{1}\vee\cdots\vee x_{m}\neq_{i_{m}}y_{m}\vee
z_{1}\;\circ\;z_{0},$ (7)

where $i_{j}\in\\{1,2\\}$,
$\circ\in\\{<_{1},\leq_{1},=_{1},<_{2},\leq_{2},=_{2}\\}$, it is permitted
that $m=0$ and the last disjunct may be omitted. With this in mind,
$\operatorname{ve}(\phi)$ (as defined just before Proposition 56) is the
desired Ord-Horn definition of $R$ viewed as a relation of arity $8$ over
$\mathbb{Q}$. By Lemma 45, we may focus on the situation when
$\theta_{i}(f_{i})\in\\{\min_{3},\operatorname{mx}_{3},\operatorname{mi}_{3},\operatorname{ll}_{3}\\}$
(since an Ord-Horn definition with reversed ordering in one of the dimensions
results in an Ord-Horn definition again).

Let $\phi(u_{1},u_{2},v_{1},v_{2})$ be the first-order definition of
$I^{-1}(R)$ over $(\mathbb{Q}^{2};<_{1},=_{1},<_{2},=_{2})$. By the definition
of $I$, if $I(u_{1},u_{2})=u$, then $u_{1}<_{1}u_{2}\wedge u_{1}<_{2}u_{2}$
and if $I(v_{1},v_{2})=v$, then $v_{1}<_{1}v_{2}\wedge v_{1}<_{2}v_{2}$.
Therefore, $\phi$ implies that the four conjuncts above hold.

Suppose first that $\theta_{i}(f_{i})=\operatorname{ll}_{3}$, $i=1,2$, then,
by Proposition 17 and Theorem 38,
$\theta_{i}(\operatorname{Pol}(\mathfrak{B}^{\prime}))$ contains an
$\operatorname{ll}$-operation for both $i$. By Proposition 56, we may assume
that $\phi$ is a conjunction of clauses of the form

$x_{1}\neq_{i_{1}}y_{1}\vee\cdots\vee x_{m}\neq_{i_{m}}y_{m}\vee
z_{1}<_{j}z_{0}\vee\cdots\vee
z_{\ell}<_{j}z_{0}\vee(z_{0}=_{j}z_{1}=_{j}\cdots=_{j}z_{\ell})$

for $i_{1},\dots,i_{m},j\in\\{1,2\\}$ and where the last disjunct may be
omitted. Since $\phi$ implies $u_{1}<_{1}u_{2}$, $u_{1}<_{2}u_{2}$,
$v_{1}<_{1}v_{2}$ and $v_{1}<_{2}v_{2}$, we may add these conjuncts to $\phi$
without loss of generality; note that the formula is still of the required
form. By an analogous argument as in the proof of Theorem 73, we can assume
that $\phi$ is of the form (7).

Next, let
$\theta_{1}(f_{1})\in\\{\min_{3},\operatorname{mx}_{3},\operatorname{mi}_{3}\\}$
and $\theta_{2}(f_{2})=\operatorname{ll}_{3}$. As in the previous paragraph,
$\theta_{2}(\operatorname{Pol}(\mathfrak{B}^{\prime}))$ contains an
$\operatorname{ll}$-operation. Similarly, by Proposition 17 and Proposition
32, $\theta_{1}(\operatorname{Pol}(\mathfrak{B}^{\prime})$ contains a
$\operatorname{pp}$-operation. By Proposition 54, $R$ may be defined by a
conjunction of weakly $1$-determined clauses of the form

$\displaystyle u_{1}\neq_{2}v_{1}\vee\cdots u_{m}\neq_{2}v_{m}\vee
y_{1}\neq_{1}x\vee\cdots\vee y_{k}\neq_{1}x\vee z_{1}\leq_{1}x\vee\cdots\vee
z_{l}\leq_{1}x$

together with $2$-determined clauses of the form

$\displaystyle x_{1}\neq_{2}y_{1}\vee\cdots\vee x_{m}\neq_{2}y_{m}\vee
z_{1}<_{2}z_{0}\vee\cdots\vee
z_{\ell}<_{2}z_{0}\vee(z_{0}=_{2}z_{1}=_{2}\cdots=_{2}z_{\ell}).$

Again, we may add the implied conjuncts $u_{1}<_{1}u_{2}$, $u_{1}<_{2}u_{2}$,
$v_{1}<_{1}v_{2}$ and $v_{1}<_{2}v_{2}$ to the defining formula. Now we may
use the same arguments as in the proof of Theorem 73 to prove that each of the
clauses may be taken to be a clause of the form (7). The proof with the two
dimensions exchanged is analogous.

Finally, assume that
$\theta_{i}(f_{i})\in\\{\min_{3},\operatorname{mx}_{3},\operatorname{mi}_{3}\\}$
for $i\in\\{1,2\\}$. We can reason analogously to the previous paragraph and
conclude that $\theta_{i}(\operatorname{Pol}(\mathfrak{B}^{\prime}))$,
$i\in\\{1,2\\}$, contains a $\operatorname{pp}$-operation. Furthermore,
Theorem 38 implies that we may assume that
$\theta_{i}(\operatorname{Pol}(\mathfrak{B}^{\prime}))$, $i\in\\{1,2\\}$, does
not contain a $\operatorname{lex}$-operation (otherwise it would contain an
$\operatorname{ll}$-operation and this case would be covered by one of the
previous cases). By applying Proposition 55 twice (the second time with the
roles of the dimensions exchanged), every relation of $\mathfrak{B}^{\prime}$
can be defined by a formula $\psi_{1}\wedge\psi_{2}$ such that $\psi_{i}$ is a
conjunction of clauses of the form

$y_{1}\neq_{i}x\vee\cdots\vee y_{k}\neq_{i}x\vee z_{1}\leq_{i}x\vee\cdots\vee
z_{l}\leq_{i}x.$

As in the previous cases, we may add the conjuncts $u_{1}<_{1}u_{2}$,
$u_{1}<_{2}u_{2}$, $v_{1}<_{1}v_{2}$ and $v_{1}<_{2}v_{2}$ to the formula
$\psi_{1}\wedge\psi_{2}$ without loss of generality. Now we may proceed
analogously to the proof of Theorem 73 and show that if the formula is
reduced, it is of the form (7). ∎

Balbiani et al. [BCdC99] have presented a tractable subclass—consisting of the
so-called strongly preconvex relations—of the rectangle algebra. They write
the following on page 447.

> The subclass generated by the set of the strongly preconvex relations is now
> the biggest known tractable set of RA which contains the 169 atomic
> relations. An open question is: is this subclass a maximal tractable
> subclass which contains the atomic relations?

We answer their question affirmatively. We know that every basic RA relation
has a primitive positive definition in $({\mathbb{I}}^{2};\hbox{\sf
m}_{1},\hbox{\sf m}_{2})$, and we observed in the beginning of this section
that the relation ${\sf m}_{1}$ is primitively positively definable with the
aid of the basic relations $({\sf m}|{\sf p})$ and $(\equiv\\!|{\sf p})$, and
${\sf m}_{2}$ is analogously primitively positively definable from $({\sf
p}|{\sf m})$ and $({\hbox{\sf p}}|\\!\equiv)$. We have thus proved (via
Theorem 78) that the Rectangle Algebra contains a single maximal subclass that
is polynomial-time solvable and contains all basic relations. The relations in
this subclass are definable via Ord-Horn formulas, and Balbiani et al.
[BCdC02, Section 6.2] have proved that strongly preconvex relations coincide
with Ord-Horn-definable relations.

We continue by analysing the $n$-dimensional block algebra when $n>2$. The
approach is similar to the approach used for the rectangle algebra: we use
complexity transfer to deduce a classification for first-order expansions of
$({\mathbb{I}}^{n};\hbox{\sf m}_{1},\dots,\hbox{\sf m}_{n})$ from the
classification for first-order expansions of
$(\mathbb{Q}^{n};<_{1},=_{1},\dots,<_{n},=_{n})$. The relations $\hbox{\sf
m}_{1},\dots,\hbox{\sf m}_{n}$ are primitively positively definable from the
basic relations of the $n$-dimensional block algebra, so we obtain in
particular a classification of the complexity of the CSP for all first-order
expansions of the basic relations of the $n$-dimensional block algebra.

######  Theorem 79.

Let $\mathfrak{D}$ be a first-order expansion of the structure
$({\mathbb{I}}^{n};\hbox{\sf m}_{1},\dots,\hbox{\sf m}_{n})$. Then there
exists a first-order expansion $\mathfrak{C}$ of
$({\mathbb{Q}}^{n};<_{1},=_{1},\dots,<_{n},=_{n})$ such that $\mathfrak{D}$
has a 2-dimensional primitive positive interpretation in $\mathfrak{C}$ and
$\mathfrak{C}$ has a 1-dimensional primitive positive interpretation in
$\mathfrak{D}$. Furthermore, exactly one of the following two cases applies.

  * •

$\mathfrak{D}$ has a pwnu polymorphism. If the signature of $\mathfrak{D}$ is
finite, then $\operatorname{CSP}(\mathfrak{D})$ is in P.

  * •

There exists a uniformly continuous minor-preserving map from
$\operatorname{Pol}(\mathfrak{D})$ to $\operatorname{Pol}(K_{3})$ and
$\mathfrak{D}$ has a finite-signature reduct whose $\operatorname{CSP}$ is NP-
complete.

###### Proof.

Straightforward generalisation of Theorem 77. ∎

It has been known for a long time that the set of Ord-Horn-definable relations
is a tractable fragment of the $n$-dimensional Block Algebra [BCdC02]. In that
article (pp. 907–908), Balbiani et al. note the following.

> The problem of the maximality of this tractable subset [Ord-Horn] remains an
> open problem. Usually to prove the maximality of a fragment of a relational
> algebra an extensive machine-generated analysis is used. Because of the huge
> size … we cannot proceed in the same way.

We answer this question in the affirmative: the subset of relations in
$\mathfrak{BA}_{n}$ that can be viewed as arity-$4n$ relations with an Ord-
Horn definition, is a maximal tractable subclass. Furthermore, it is the only
maximal subclass that is tractable and contains all basic relations. To see
this, we proceed in the same way as in the analysis of the Rectangle Algebra.
First of all, every basic relation in $\mathfrak{BA}_{n}$ has a primitive
positive definition in $({\mathbb{I}}^{n};\hbox{\sf m}_{1},\dots,\hbox{\sf
m}_{n})$, and the relations $\hbox{\sf m}_{1},\dots,\hbox{\sf m}_{n}$ are
easily seen to be primitively positive definable in the basic relations of
$\mathfrak{BA}_{n}$. It follows from the corollary below that the only maximal
subclass of $\mathfrak{BA}_{n}$ that is polynomial-time solvable and contains
all basic relations is the Ord-Horn class.

######  Corollary 80.

Let $\mathfrak{B}$ be a binary first-order expansion of
$(\mathbb{I}^{n};\hbox{\sf m}_{1},\dots,\hbox{\sf m}_{n})$. Then exactly one
of the following cases applies.

  * •

Each relation in $\mathfrak{B}$, viewed as a relation of arity $4n$ over
${\mathbb{Q}}$, has an Ord-Horn definition. In this case, $\mathfrak{B}$ has a
pwnu polymorphism and $\operatorname{CSP}(\mathfrak{B})$ is in P.

  * •

$\operatorname{Pol}(\mathfrak{B})$ has a uniformly continuous minor-preserving
map to $\operatorname{Pol}(K_{3})$ and $\mathfrak{B}$ has a finite-signature
reduct whose $\operatorname{CSP}$ is NP-complete.

###### Proof.

Recall Theorem 79 and let $\mathfrak{B}^{\prime}$ be the first-order expansion
of $({\mathbb{Q}}^{n};<_{1},=_{1},\dots,<_{n},=_{n})$ such that $\mathfrak{B}$
has a 2-dimensional primitive positive interpretation $I$ in
$\mathfrak{B}^{\prime}$ and $\mathfrak{B}^{\prime}$ has a 1-dimensional
primitive positive interpretation in $\mathfrak{B}$. By combining Corollary
12, Lemma 10 and Theorem 64, we deduce by the same argumentation as in the
proof of Theorem 78 that if the statement in the second item does not hold,
then $\mathfrak{B}^{\prime}$ and $\mathfrak{B}$ have a pwnu polymorphism and
$\operatorname{CSP}(\mathfrak{B}^{\prime})$ and
$\operatorname{CSP}(\mathfrak{B})$ are in P. Moreover, in this case, Theorem
64 implies that for every $p\in\\{1,\dots,n\\}$, there is an
$f_{p}\in\operatorname{Pol}(\mathfrak{B}^{\prime})$ such that
$\theta_{p}(f_{p})$ equals $\min_{3}$, $\operatorname{mx}_{3}$,
$\operatorname{mi}_{3}$, $\operatorname{ll}_{3}$, or one of their duals.

It remains to show that if $\operatorname{CSP}(\mathfrak{B})$ is in P, then
every (binary) relation of $\mathfrak{B}$, considered as a relation of arity
$4n$ over ${\mathbb{Q}}$, has an Ord-Horn definition. Let $R$ be a relation of
$\mathfrak{B}$. Observe that, as in the proof of Theorem 78, it is enough to
show that the $4$-ary relation $I^{-1}(R)$ has a definition
$\phi(u_{1},u_{2},v_{1},v_{2})$ that is a conjunction of clauses of the form

$x_{1}\neq_{i_{1}}y_{1}\vee\cdots\vee x_{m}\neq_{i_{m}}y_{m}\vee
z_{1}\;\circ\;z_{0},$ (8)

where $i_{j}\in\\{1,\dots,n\\}$,
$\circ\in\\{<_{1},\leq_{1},=_{1},\dots,<_{n},\leq_{n},=_{n}\\}$, it is
permitted that $m=0$ and the last disjunct may be omitted; then
$\operatorname{ve}(\phi)$ will be the desired Ord-Horn definition of $R$
viewed as a relation of arity $4n$ over $\mathbb{Q}$.

By Lemma 45, we may focus on the situation that
$f_{p}\in\\{\min_{3},\operatorname{mx}_{3},\operatorname{mi}_{3},\operatorname{ll}_{3}\\}$
for every $p\in\\{1,\dots,n\\}$. Therefore, by Proposition 32 and Theorem 38,
there is a set $S\subseteq\\{1,\dots,n\\}$ such that, for each $p\in S$,
$\theta_{p}(\operatorname{Pol}(\mathfrak{B}^{\prime})$ contains an
$\operatorname{ll}$-operation and, for each $p\in\\{1,\dots,n\\}\setminus S$,
$\theta_{p}(\operatorname{Pol}(\mathfrak{B}^{\prime})$ contains a
$\operatorname{pp}$-operation but not a $\operatorname{lex}$-operation. We may
therefore assume that $\phi$ has the syntactic form described in Proposition
62. Moreover, we may assume that $\phi$ contains the conjuncts
$u_{1}<_{j}u_{2}$ and $v_{1}<_{j}v_{2}$, $j=1,\dots,n$, since these are
implied by $\phi$ (see the proof of Theorem 78 for more details). For each of
the two types of clauses that appear in $\phi$, we may use the same case
distinction as in Theorems 73 and 78 to show that each of the clauses is of
the form (8). This concludes the proof. ∎

Balbiani et al. [BCdC02, p. 908] also raise the following question:

> …the question also arises as to how the qualitative constraints [Block
> Algebra] we have been considering could be integrated into a more general
> setting to include metric constraints.

If one focuses on tractable subclasses that contain all basic relations, then
such an integration is indeed possible. Since our results imply that the
relations in such a tractable subclass must be definable via Ord-Horn
formulas, they can immediately be embedded into the metric framework suggested
by Jonsson and Bäckström [JB98] and Koubarakis [Kou01]. Under the same
assumptions, this holds for the cardinal direction calculus and Allen’s
Interval Algebra, too.

##  7 Conclusions and Open Problems

We prove that the CSPs for first-order expansions of $({\mathbb{Q}};<)^{(n)}$
satisfy a complexity dichotomy: they are in P or NP-complete. Using a general
complexity transfer method, we prove that first-order expansions of the basic
relations of the cardinal direction calculus, Allen’s Interval Algebra, and
the $n$-dimensional block algebra have a CSP complexity dichotomy. Less
obviously, the complexity transfer method can also be applied to show that
first-order expansions of the relations ${\sf s}$ and ${\sf f}$ of Allen’s
Interval Algebra have a complexity dichotomy. All of the results can be
specialised for binary signatures, in which case we obtain new and
conceptually simple proofs of results that have first been shown with the help
of a computer (Theorem 73) or that answer several questions from the
literature (Section 6.3).

Our results also imply that the so-called _meta-problem_ of complexity
classification is decidable: given finitely many first-order formulas that
define a first-order expansion $\mathfrak{D}$ of one of the structures for
which we obtained a complexity classification, one can effectively decide
whether $\operatorname{CSP}(\mathfrak{D})$ is in P or NP-complete. There are
several ways to prove this. One way is to use our syntactic normal form
results for the tractable cases to obtain such an algorithm. However, we may
also use the general fact that for homogeneous finitely bounded structures
that are model-complete cores and have an extremely amenable automorphism
group (all of these assumptions are satisfied by our structures) the condition
of the tractability conjecture (see Corollary 12) can be decided effectively
(essentially by checking exhaustively for the existence of a _diagonally
canonical pseudo Siggers polymorphism_); since these results are not new we
refer to [Bod21, Section 11.6] for details.

One may wonder about first-order reducts of $({\mathbb{Q}};<)^{(n)}$ or
structures that are first-order interpretable in $({\mathbb{Q}};<)^{(n)}$
rather than just first-order expansions. Classifying the complexity of the CSP
for such structures will be a challenging project since the set of possible
structures includes, for instance, finite-domain structures, all stable
finitely homogeneous structures [Lac92], and the infinite Johnson graphs
$J(\omega,n)$ (for example, the line graph of the countably infinite clique
when $n=2$). Such a project would also include the following interesting
classification problem.

The _age_ of a relational structure $\mathfrak{B}$ is the class of all finite
structures that embed into $\mathfrak{B}$. It follows from Fraïssé’s theorem
(or by a direct back-and-forth argument) that two homogeneous structures with
the same age are isomorphic (see, e.g. [Hod97, Theorem 6.1.2]). Let
$\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ be homogeneous structures with
disjoint relational signatures $\tau_{1}$ and $\tau_{2}$ and without
algebraicity (see [Hod97]; the structure $({\mathbb{Q}};<)$ is an example of
such a structure without algebraicity). It is well known that there exists an
up to isomorphism unique countable homogeneous
$(\tau_{1}\cup\tau_{2})$-structure whose age consists of all structures whose
$\tau_{1}$-reduct is in the age of $\mathfrak{A}_{1}$ and whose
$\tau_{2}$-reduct is in the age of $\mathfrak{A}_{2}$; this structure is
called the _generic combination_ of $\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$,
and will be denoted by $\mathfrak{A}_{1}*\mathfrak{A}_{2}$. It can be shown by
a back-and-forth argument that the $\tau_{1}$-reduct of
$\mathfrak{A}_{1}*\mathfrak{A}_{2}$ is isomorphic to $\mathfrak{A}_{1}$ and
the $\tau_{2}$-reduct is isomorphic to $\mathfrak{A}_{2}$. One may note that
the notion of generic combinations can be defined also for
$\omega$-categorical structures without algebraicity [BG20]. If
$\mathfrak{A}_{1}$ and $\mathfrak{A}_{2}$ are first-order reducts of
$({\mathbb{Q}};<)$ then the complexity of
$\operatorname{CSP}(\mathfrak{A}_{1}*\mathfrak{A}_{2})$ has been classified
recently [BGR20]. A complexity classification of
$\operatorname{CSP}(\mathfrak{B})$ for first-order reducts $\mathfrak{B}$ of
$({\mathbb{Q}};<)*({\mathbb{Q}};<)$, however, is open.

######  Proposition 81.

For every first-order reduct $\mathfrak{B}$ of
$({\mathbb{Q}};<)*({\mathbb{Q}};<)$, there exists a first-order reduct
$\mathfrak{C}$ of $({\mathbb{Q}};<)\boxtimes({\mathbb{Q}};<)$ such that
$\mathfrak{C}$ is homomorphically equivalent to $\mathfrak{B}$.

###### Proof.

Let $\mathfrak{A}$ be the $\\{<_{1},<_{2}\\}$-reduct of
$({\mathbb{Q}};<)\boxtimes({\mathbb{Q}};<)$. For $i\in\\{1,2\\}$ there exists
an isomorphism $\alpha_{i}$ between the $\\{<_{i}\\}$-reduct of
$({\mathbb{Q}};<)*({\mathbb{Q}};<)$ and $({\mathbb{Q}};<)$. Then $e\colon
d\mapsto(\alpha_{1}(d),\alpha_{2}(d))$ is an embedding of
$({\mathbb{Q}};<)*({\mathbb{Q}};<)$ into $\mathfrak{A}$. Conversely, if we fix
a linear extension of $<_{1}$ and $<_{2}$ in
$({\mathbb{Q}};<)\boxtimes({\mathbb{Q}};<)$, then the
$\\{<_{1},<_{2}\\}$-reduct of the resulting structure embeds into
$({\mathbb{Q}};<)*({\mathbb{Q}};<)$ (see, e.g., [Bod21, Lemma 4.1.7]). This
shows that $\mathfrak{A}$ has an injective homomorphism $h$ to
$({\mathbb{Q}};<)*({\mathbb{Q}};<)$.

Let $\mathfrak{B}$ be a first-order reduct of
$({\mathbb{Q}};<)*({\mathbb{Q}};<)$. Every first-order formula $\phi$ over
$({\mathbb{Q}};<)*({\mathbb{Q}};<)$ is equivalent to a quantifier-free formula
in conjunctive normal form, because $({\mathbb{Q}};<)*({\mathbb{Q}};<)$ is
homogeneous and $\omega$-categorical. Replace each atomic subformula of $\phi$
of the form $\neg(x<_{i}y)$, for $i\in\\{1,2\\}$, by $y<_{i}x\vee x=y$. Then
replace each subformula of the form $x\neq y$ by $x<_{1}y\vee y<_{1}x$. The
resulting formula is equivalent over $({\mathbb{Q}};<)*({\mathbb{Q}};<)$. Each
formula that defines a relation of $\mathfrak{B}$ and is written in this form
can be interpreted over $({\mathbb{Q}};<)\boxtimes({\mathbb{Q}};<)$ instead of
$({\mathbb{Q}};<)*({\mathbb{Q}};<)$; let $\mathfrak{C}$ be the obtained first-
order reduct of $({\mathbb{Q}};<)\boxtimes({\mathbb{Q}};<)$.

Since the first-order definitions of the relations of $\mathfrak{B}$ are
quantifier-free, the embedding $e$ of $({\mathbb{Q}};<)*({\mathbb{Q}};<)$ into
$\mathfrak{A}$ is also an embedding of $\mathfrak{B}$ into $\mathfrak{C}$. We
claim that $h$ is a homomorphism from $\mathfrak{C}$ to $\mathfrak{B}$. This
follows from the fact that $h$ is a homomorphism from
$({\mathbb{Q}};<)\boxtimes({\mathbb{Q}};<)$ to $\mathfrak{A}$ and that the
defining formulas for the relations of $\mathfrak{B}$ and $\mathfrak{C}$ do
not involve negation. ∎

Another way forward is to study basic structures other than
$({\mathbb{Q}};<)$. Here, temporal reasoning is a source of examples with
applications in, for instance, AI. An important time model used in temporal
reasoning is branching time, where for every point in time the past is
linearly ordered, but the future is partially ordered. This motivates the so-
called left-linear point algebra [Dün05, Hir97], which is a relation algebra
with four basic relations, denoted by $=$, $<$, $>$, and $|$. Here, $x|y$
signifies that $x$ and $y$ are incomparable in time, and ‘$x<y$’ signifies
that $x$ is earlier in time than $y$. The branching-time satisfiability
problem can be formulated as CSP$(\mathfrak{B})$ for an $\omega$-categorical
structure $\mathfrak{B}$ [BN06]. One possible concrete description of the
structure $\mathfrak{B}$, described by Adeleke and Neumann [AN98], is to let
$\mathfrak{B}=(B;<,|,=)$ where $B$ is the set of finite sequences of rational
numbers. For arbitrary $a=(a_{1},\dots,a_{n})$ and $b=(b_{1},\dots,b_{m})$ in
$B$ with $n\leq m$, $a<b$ holds if one of the following conditions hold:

  1. 1.

$n<m$ and $a_{i}=b_{i}$ for $1\leq i\leq n$, or

  2. 2.

$a_{i}=b_{i}$ for $1\leq i<n$ and $a_{n}<b_{n}$.

The remaining relations are defined in the obvious way.

Branching time has been used, for example, in automated planning [DB88], as
the basis for temporal logics [EH86], and as the basis for a generalisation of
Allen’s Interval Algebra [RW04]. In particular, the complexity of the
branching variant222Various ways of defining the formalism are possible
[RW04]. We restrict our attention to the most well-known end-point-based
formalism that contains 19 basic relations. of Allen’s Interval Algebra has
recently gained attraction [BGP+21, BGST20, BGP+20, GPS18, DS18]. Some
complexity results for the branching interval algebra $\mathfrak{B}$ are
presented in these publications, but the big picture is missing, even for
first-order expansions of the basic relations. Our classification transfer
result (Theorem 69) is applicable to this problem, but since there is
currently no complexity classification of the CSPs for first-order reducts of
${\mathfrak{B}}$, we cannot present a full classification for CSPs of first-
order expansions of the basic branching interval relations. Naturally, there
is no polymorphism-based description of the tractable fragments either, so we
cannot analyse the complexity of CSPs for first-order expansions of the
structure $(B^{n};<_{1},|_{1},=_{1},\dots,<_{n},|_{n},=_{n})$ in the style of
Theorem 64. However, given a complexity classification of the CSPs for first-
order expansions of $\mathfrak{B}$ in place, then Theorem 69 is immediately
applicable, and we do not see any fundamental problem that prevents us from
generalising Theorem 64 to expansions of
$(B^{n};<_{1},|_{1},=_{1},\dots,<_{n},|_{n},=_{n})$ as long as the tractable
fragments can be described via polymorphisms and nice syntactic normal forms.

A related time model encountered in computer science is partially ordered time
(po-time). This model has various applications in, for instance, the analysis
of concurrent and distributed systems [Ang89, Lam86]. In po-time, both the
past and the future of a time point are partially ordered. This implies that
time becomes a partial order with four basic relations $=$, $<$, $>$ and $|$,
signifying “equal”, “before”, “after” and “unrelated”, respectively. The
satisfiability problem for po-time can convieniently be formulated with the
random partial order $(P;<)$, and Kompatscher and Van Pham [KP18] have
presented a full complexity classification of the CSP for all first-order
reducts of the random partial order. Combined with Theorem 69, this gives us a
full classification of the CSP for first-order expansions of the basic
relations of the po-time analogue of the interval algebra. This generalisation
of the interval algebra has been studied by Zapata et al. [ZKJH13].
Kompatscher and Van Pham describe the tractable fragments of the random
partial order with the aid of polymorphisms. Hence, it seems conceivable that
their result can be generalised to a complexity classification of the CSP for
first-order expansions of $(P^{n};<_{1},|_{1},=_{1},\dots,<_{n},|_{n},=_{n})$
by utilising the ideas behind the proof of Theorem 64.

## Acknowledgements

We thank Johannes Greiner for his comments on an earlier version of this
article.

## References

  * [AH85] James F. Allen and Patrick J. Hayes.  A common-sense theory of time.  In Proc. 9th International Joint Conference on Artificial Intelligence (IJCAI-1985), pages 528–531, 1985.
  * [All83] James F. Allen.  Maintaining knowledge about temporal intervals.  Communications of the ACM, 26(11):832–843, 1983.
  * [AN98] Samson Adepoju Adeleke and Peter M. Neumann.  Relations related to betweenness: their structure and automorphisms.  Memoirs of the American Mathematical Society, 131(623):viii+125, 1998.
  * [Ang89] Frank D. Anger.  On Lamport’s interprocessor communication model.  ACM Transactions on Programming Languages and Systems, 11(3):404–417, 1989.
  * [AZ86] Gisela Ahlbrandt and Martin Ziegler.  Quasi-finitely axiomatizable totally categorical theories.  Annals of Pure and Applied Logic, 30(1):63–82, 1986.
  * [BB21] Manuel Bodirsky and Bertalan Bodor.  Canonical polymorphisms of Ramsey structures and the unique interpolation property.  In Proc. 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS-2021), pages 1–13, 2021.
  * [BC02] Philippe Balbiani and Jean-François Condotta.  Spatial reasoning about points in a multidimensional setting.  Applied Intelligence, 17(3):221–238, 2002.
  * [BCdC99] Philippe Balbiani, Jean-François Condotta, and Luis Fariñas del Cerro.  A new tractable subclass of the rectangle algebra.  In Proc. 16th International Joint Conference on Artificial Intelligence (IJCAI-1999), pages 442–447, 1999.
  * [BCdC02] Philippe Balbiani, Jean-François Condotta, and Luis Fariñas del Cerro.  Tractability results in the block algebra.  Journal of Logic and Computation, 12(5):885–909, 2002.
  * [BCW14] Manuel Bodirsky, Hubie Chen, and Michał Wrona.  Tractability of quantified temporal constraints to the max.  International Journal of Algebra and Computation, 24(8):1141–1156, 2014.
  * [BG08] Manuel Bodirsky and Martin Grohe.  Non-dichotomies in constraint satisfaction complexity.  In Proc. 35th International Colloquium on Automata, Languages and Programming (ICALP-2008), pages 184 –196, 2008.
  * [BG20] Manuel Bodirsky and Johannes Greiner.  The complexity of combinations of qualitative constraint satisfaction problems.  Logical Methods in Computer Science, 16(1), 2020.
  * [BGP+20] Alessandro Bertagnon, Marco Gavanelli, Alessandro Passantino, Guido Sciavicco, and Stefano Trevisani.  The Horn fragment of branching algebra.  In Proc. 27th International Symposium on Temporal Representation and Reasoning (TIME-2020), pages 5:1–5:16, 2020.
  * [BGP+21] Alessandro Bertagnon, Marco Gavanelli, Alessandro Passantino, Guido Sciavicco, and Stefano Trevisani.  Branching interval algebra: An almost complete picture.  Information and Computation, 281:104809, 2021.
  * [BGR20] Manuel Bodirsky, Johannes Greiner, and Jakub Rydval.  Tractable combinations of temporal CSPs.  CoRR, abs/2012.05682, 2020.
  * [BGST20] Alessandro Bertagnon, Marco Gavanelli, Guido Sciavicco, and Stefano Trevisani.  On (maximal, tractable) fragments of the branching algebra.  In Proc. 35th Italian Conference on Computational Logic (CILC-2020), pages 113–126, 2020.
  * [BJ17] Manuel Bodirsky and Peter Jonsson.  A model-theoretic view on qualitative constraint reasoning.  Journal of Artificial Intelligence Research, 58:339–385, 2017.
  * [BJMM18] Manuel Bodirsky, Peter Jonsson, Barnaby Martin, and Antoine Mottet.  Classification transfer for qualitative reasoning problems.  In Proc. 27th International Joint Conference on Artificial Intelligence (IJCAI-2018), pages 1256–1262, 2018.
  * [BJP17] Manuel Bodirsky, Peter Jonsson, and Trung Van Pham.  The complexity of phylogeny constraint satisfaction problems.  ACM Transactions on Computational Logic, 18(3):23:1–23:42, 2017\.
  * [BK09] Manuel Bodirsky and Jan Kára.  The complexity of temporal constraint satisfaction problems.  Journal of the ACM, 57(2):1–41, 2009.
  * [BK10] Manuel Bodirsky and Jan Kára.  A fast algorithm and Datalog inexpressibility for temporal reasoning.  ACM Transactions on Computational Logic, 11(3), 2010.
  * [BK21] Manuel Bodirsky and Simon Knäuer.  Network satisfaction for symmetric relation algebras with a flexible atom.  In Proc. 35th AAAI Conference on Artificial Intelligence (AAAI-2021), pages 6218–6226, 2021.
  * [BKO+19] Libor Barto, Michael Kompatscher, Miroslav Olšák, Trung Van Pham, and Michael Pinsker.  Equations in oligomorphic clones and the constraint satisfaction problem for $\omega$-categorical structures.  Journal of Mathematical Logic, 19(2):#1950010, 2019.
  * [BM18] Manuel Bodirsky and Antoine Mottet.  A dichotomy for first-order reducts of unary structures.  Logical Methods in Computer Science, 14(2), 2018.
  * [BMM21] Manuel Bodirsky, Florent R. Madelaine, and Antoine Mottet.  A proof of the algebraic tractability conjecture for monotone monadic SNP.  SIAM Journal on Computing, 50(4):1359–1409, 2021.
  * [BMPP19] Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz.  Constraint satisfaction problems for reducts of homogeneous graphs.  SIAM Journal on Computing, 48(4):1224–1264, 2019.
  * [BN06] Manuel Bodirsky and Jaroslav Nešetřil.  Constraint satisfaction with countable homogeneous templates.  Journal of Logic and Computation, 16(3):359–373, 2006.
  * [Bod21] Manuel Bodirsky.  Complexity of Infinite-Domain Constraint Satisfaction.  Cambridge University Press, 2021.
  * [BOP18] Libor Barto, Jakub Opršal, and Michael Pinsker.  The wonderland of reflections.  Israel Journal of Mathematics, 223(1):363–398, 2018.
  * [BP15a] Manuel Bodirsky and Michael Pinsker.  Schaefer’s theorem for graphs.  Journal of the ACM, 62(3):19:1–19:52, 2015.
  * [BP15b] Manuel Bodirsky and Michael Pinsker.  Topological Birkhoff.  Transactions of the American Mathematical Society, 367:2527–2549, 2015.
  * [BP16] Libor Barto and Michael Pinsker.  The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems.  In Proc. 31th Annual IEEE Symposium on Logic in Computer Science (LICS-2016), pages 615–622, 2016.
  * [BP21] Manuel Bodirsky and Michael Pinsker.  Canonical functions: a proof via topological dynamics.  Contributions to Discrete Mathematics, 16(2):36–45, 2021.
  * [BPP21] Manuel Bodirsky, Michael Pinsker, and András Pongrácz.  Projective clone homomorphisms.  Journal of Symbolic Logic, 86(1):148–161, 2021.
  * [BPR20] Manuel Bodirsky, Wied Pakusa, and Jakub Rydval.  Temporal constraint satisfaction problems in fixed-point logic.  In Proc. 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS-2020), pages 237–251, 2020.
  * [BPT13] Manuel Bodirsky, Michael Pinsker, and Todor Tsankov.  Decidability of definability.  Journal of Symbolic Logic, 78(4):1036–1054, 2013.
  * [BR20] Franz Baader and Jakub Rydval.  Description logics with concrete domains and general concept inclusions revisited.  In Proc. 10th International Joint Conference on Automated Reasoning (IJCAR-2020), pages 413–431, 2020.
  * [BS03] Andrei A. Bulatov and Evgeny S. Skvortsov.  Amalgams of constraint satisfaction problems.  In Proc. 18th International Joint Conference on Artificial Intelligence (IJCAI-2003), pages 197–202, 2003.
  * [BtCLW14] Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter.  Ontology-based data access: A study through disjunctive Datalog, CSP, and MMSNP.  ACM Transactions of Database Systems, 39(4):33, 2014.
  * [Bul17] Andrei A. Bulatov.  A dichotomy theorem for nonuniform CSPs.  In Proc. 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS-2017), pages 319–330, 2017.
  * [Cam76] Peter J. Cameron.  Transitivity of permutation groups on unordered sets.  Mathematische Zeitschrift, 148:127–139, 1976.
  * [Che19] Artem Chernikov.  Lecture Notes on Stability Theory.  AMS Open Math Notes, 2019.
  * [DB88] Thomas L. Dean and Mark S. Boddy.  Reasoning about partially ordered events.  Artificial Intelligence, 36(3):375–399, 1988.
  * [DS18] Salih Durhan and Guido Sciavicco.  Allen-like theory of time for tree-like structures.  Information and Computation, 259(3):375–389, 2018.
  * [Dün05] Ivo Düntsch.  Relation algebras and their application in temporal and spatial reasoning.  Artificial Intelligence Review, 23:315–357, 2005.
  * [EH86] E. Allen Emerson and Joseph Y. Halpern.  “Sometimes” and “not never” revisited: on branching versus linear time temporal logic.  Journal of the ACM, 33(1):151–178, 1986.
  * [FV99] Tomás Feder and Moshe Y. Vardi.  The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory.  SIAM Journal on Computing, 28:57–104, 1999.
  * [GPS18] Marco Gavanelli, Alessandro Passantino, and Guido Sciavicco.  Deciding the consistency of branching time interval networks.  In Proc. 25th International Symposium on Temporal Representation and Reasoning (TIME-2018), pages 12:1–12:15, 2018.
  * [Gre21] Johannes Greiner.  Complexity of Constraint Satisfaction Problems for Unions of Theories.  PhD thesis, Technischen Universität Dresden, 2021.
  * [Gue89] Hans Guesgen.  Spatial reasoning based on Allen’s temporal logic.  Report ICSI TR 89-049, International Computer Science Institute, 1989\.
  * [Hir97] Robin Hirsch.  Expressive power and complexity in algebraic logic.  Journal of Logic and Computation, 7(3):309 – 351, 1997.
  * [Hod97] Wilfrid Hodges.  A shorter model theory.  Cambridge University Press, Cambridge, 1997.
  * [JB98] Peter Jonsson and Christer Bäckström.  A unifying approach to temporal constraint reasoning.  Artificial Intelligence, 102(1):143–155, 1998.
  * [Jea98] Peter G. Jeavons.  On the algebraic structure of combinatorial problems.  Theoretical Computer Science, 200:185–204, 1998.
  * [KJJ03] Andrei A. Krokhin, Peter Jeavons, and Peter Jonsson.  Reasoning about temporal relations: The tractable subalgebras of Allen’s interval algebra.  Journal of the ACM, 50(5):591–640, 2003.
  * [Kou01] Manolis Koubarakis.  Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning.  Theoretical Computer Science, 266:311–339, 2001.
  * [KP18] Michael Kompatscher and Trung Van Pham.  A complexity dichotomy for poset constraint satisfaction.  IfCoLog Journal of Logics and their Applications, 5(8):1663–1696, 2018.
  * [KPT05] Alexander Kechris, Vladimir Pestov, and Stevo Todorčević.  Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups.  Geometric and Functional Analysis, 15(1):106–189, 2005.
  * [KV98] Phokion G. Kolaitis and Moshe Y. Vardi.  Conjunctive-query containment and constraint satisfaction.  In Proc. 17th Symposium on Principles of Database Systems (PODS-1998), pages 205–213, 1998.
  * [Lac92] Alistair H. Lachlan.  $\aleph_{0}$-categorical tree-decomposable structures.  Journal of Symbolic Logic, 57(2):501–514, 1992.
  * [Lam86] Leslie Lamport.  The mutual exclusion problem: part I—a theory of interprocess communication.  Journal of the ACM, 33(2):313–326, 1986.
  * [Lig98a] Gérard Ligozat.  ”Corner” relations in Allen’s algebra.  Constraints, 3(2/3):165–177, 1998.
  * [Lig98b] Gérard Ligozat.  Reasoning about cardinal directions.  Journal of Visual Languages & Computing, 9(1):23 – 44, 1998.
  * [Lig01] Gérard Ligozat.  When tables tell it all: Qualitative spatial and temporal reasoning based on linear orderings.  In Proc. 5th International Conference on Spatial Information Theory (COSIT-2001), pages 60–75, 2001.
  * [MJ90] Amitabha Mukerjee and Gene Joe.  A qualitative model for space.  In Proc. 8th National Conference on Artificial Intelligence (AAAI-1990), pages 721–727, 1990.
  * [MM08] Miklós Maróti and Ralph McKenzie.  Existence theorems for weakly symmetric operations.  Algebra Universalis, 59(3), 2008.
  * [MNPW21] Antoine Mottet, Tomás Nagy, Michael Pinsker, and Michal Wrona.  Smooth approximations and relational width collapses.  In Proc. 48th International Colloquium on Automata, Languages, and Programming (ICALP-2021), pages 138:1–138:20, 2021.
  * [Mot14] Antoine Mottet.  A maximally tractable fragment of temporal reasoning plus successor.  MPRI Masters Dissertation, 2014.
  * [MP21] Antoine Mottet and Michael Pinsker.  Cores over Ramsey structures.  Journal of Symbolic Logic, 86(1):352–361, 2021.
  * [MP22] Antoine Mottet and Michael Pinsker.  Smooth approximations and CSPs over finitely bounded homogeneous structures.  In Proc. 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS-2022), pages 36:1–36:13, 2022.
  * [MS07] Florent Madelaine and Iain A. Stewart.  Constraint satisfaction, logic and forbidden patterns.  SIAM Journal on Computing, 37(1):132–163, 2007.
  * [MSS04] Rolf H. Möhring, Martin Skutella, and Frederik Stork.  Scheduling with and/or precedence constraints.  SIAM Journal on Computing, 33(2):393–415, 2004.
  * [NB95] Bernhard Nebel and Hans-Jürgen Bürckert.  Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra.  Journal of the ACM, 42(1):43–66, 1995.
  * [Opa79] Jaroslav Opatrný.  Total ordering problem.  SIAM Journal on Computing, 8(1):111–114, 1979.
  * [RW04] Marco Ragni and Stefan Wölfl.  Branching Allen.  In Proc. Spatial Cognition IV: Reasoning, Action, Interaction, International Conference Spatial Cognition 2004, volume 3343 of Lecture Notes in Computer Science, pages 323–343, 2004.
  * [She71] Saharon Shelah.  Stability, the f.c.p. and superstability; model theoretic properties of formulas in first order theory.  Annals of Mathematical Logic, 3:271–362, 1971.
  * [Sim15] Pierre Simon.  A Guide to NIP Theories.  Lecture Notes in Logic. Cambridge University Press, 2015.
  * [WW09] Matthias Westphal and Stefan Wölfl.  Qualitative CSP, finite CSP, and SAT: comparing methods for qualitative constraint-based reasoning.  In Proc. 21th International Joint Conference on Artificial Intelligence (IJCAI-2009), pages 628–633, 2009.
  * [Zhu20] Dmitriy Zhuk.  A proof of the CSP dichotomy conjecture.  Journal of the ACM, 67(5):30:1–30:78, 2020.
  * [ZKJH13] Francisco Zapata, Vladik Kreinovich, Cliff A. Joslyn, and Emilie Hogan.  Orders on intervals over partially ordered sets: extending Allen’s algebra and interval graph results.  Soft Computing, 17(8):1379–1391, 2013.