# On the complexity of symmetric vs. functional PCSPs††thanks: An extended
abstract of part of this work (with weaker results) will appear in the
Proceedings of LICS 2023 [28]. This work was supported by UKRI EP/X024431/1
and a Clarendon Fund Scholarship. For the purpose of Open Access, the authors
have applied a CC BY public copyright licence to any Author Accepted
Manuscript version arising from this submission. All data is provided in full
in the results section of this paper.

Tamio-Vesa Nakajima
University of Oxford
<EMAIL_ADDRESS>Stanislav Živný
University of Oxford
<EMAIL_ADDRESS>
###### Abstract

The complexity of the _promise constraint satisfaction problem_
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is largely unknown, even for
symmetric $\mathbf{A}$ and $\mathbf{B}$, except for the case when $\mathbf{A}$
and $\mathbf{B}$ are Boolean.

First, we establish a dichotomy for
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ where $\mathbf{A},\mathbf{B}$ are
symmetric, $\mathbf{B}$ is _functional_ (i.e. any $r-1$ elements of an $r$-ary
tuple uniquely determines the last one), and $(\mathbf{A},\mathbf{B})$
satisfies technical conditions we introduce called _dependency_ and
_additivity_. This result implies a dichotomy for
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ with $\mathbf{A},\mathbf{B}$
symmetric and $\mathbf{B}$ functional if (i) $\mathbf{A}$ is Boolean, or (ii)
$\mathbf{A}$ is a hypergraph of a small uniformity, or (iii) $\mathbf{A}$ has
a relation $R^{\mathbf{A}}$ of arity at least 3 such that the hypergraph
diameter of $(A,R^{\mathbf{A}})$ is at most 1.

Second, we show that for $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, where
$\mathbf{A}$ and $\mathbf{B}$ contain a single relation, $\mathbf{A}$
satisfies a technical condition called _balancedness_ , and $\mathbf{B}$ is
arbitrary, the combined _basic linear programming_ relaxation
($\operatorname{BLP}$) and the _affine integer programming_ relaxation
($\operatorname{AIP}$) is no more powerful than the (in general strictly
weaker) $\operatorname{AIP}$ relaxation. Balanced $\mathbf{A}$ include
symmetric $\mathbf{A}$ or, more generally, $\mathbf{A}$ preserved by a
transitive permutation group.

##  1 Introduction

_Promise constraint satisfaction problems_ (PCSPs) are a generalisation of
constraint satisfaction problems (CSPs) that allow for capturing many more
computational problems [4, 8, 6].

A canonical example of a CSP is the 3-colouring problem: Given a graph
$\mathbf{G}$, is it 3-colourable? This can be cast as a CSP. Let
$\mathbf{K}_{k}$ denote a clique on $k$ vertices. Then
$\operatorname{CSP}(\mathbf{K}_{3})$, the constraint satisfaction problem with
the template $\mathbf{K}_{3}$, is the following computational problem (in the
decision version): Given a graph $\mathbf{G}$, say Yes if there is a
homomorphism from $\mathbf{G}$ to $\mathbf{K}_{3}$ (indicated by
$\mathbf{G}\to\mathbf{K}_{3}$) and say No otherwise (indicated by
$\mathbf{G}\not\to\mathbf{K}_{3})$. Here a graph homomorphism is an edge
preserving map [23]. As graph homomorphisms from $\mathbf{G}$ to
$\mathbf{K}_{3}$ are $3$-colourings of $\mathbf{G}$,
$\operatorname{CSP}(\mathbf{K}_{3})$ is the $3$-colouring problem.

Another example of a CSP is 1-in-3-SAT: Given a positive 3-CNF formula, is
there an assignment that satisfies exactly one literal in each clause? This is
$\operatorname{CSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3})$,
where

$\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3}=(\\{0,1\\};\\{(1,0,0),(0,1,0),(0,0,1)\\}).$

Yet another example is NAE-3-SAT: Given a positive 3-CNF formula, is there an
assignment that satisfies one or two literals in each clause? This is
$\operatorname{CSP}(\mathbf{NAE})$, where

$\mathbf{NAE}=(\\{(0,1);{\\{0,1\\}}^{3}\setminus\\{(0,0,0),(1,1,1)\\}).$

A canonical example of a PCSP is the approximate graph colouring problem [21]:
Fix $k\leq\ell$. Given a graph $\mathbf{G}$, determine whether $\mathbf{G}$ is
$k$-colourable or not even $\ell$-colourable. (The case $k=\ell$ is the same
as $k$-colouring.) This is the same as the PCSP over cliques; i.e.,
$\operatorname{PCSP}(\mathbf{K}_{k},\mathbf{K}_{\ell})$ is the following
computational problem (in the decision version): Given a graph $\mathbf{G}$,
say Yes if $\mathbf{G}\to\mathbf{K}_{k}$ and say No if
$\mathbf{G}\not\to\mathbf{K}_{\ell}$. In the search version, one is given a
$k$-colourable graph $\mathbf{G}$ and the task is to find an $\ell$-colouring
of $\mathbf{G}$ (which necessarily exists by the promise and the fact that
$k\leq\ell$).

Another example of a PCSP is
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{NAE})$,
identified in [8]: Given a satisfiable instance $\mathbf{X}$ of
$\operatorname{CSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3})$, can
one find a solution if $\mathbf{X}$ is seen as an instance of
$\operatorname{CSP}(\mathbf{NAE})$? I.e., can one find a solution that
satisfies one or two literals in each clause given the promise that a solution
that satisfies exactly one literal in each clause exists? Although both
$\operatorname{CSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3})$ and
$\operatorname{CSP}(\mathbf{NAE})$ are NP-complete, Brakensiek and Guruswami
showed in [8] that
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{NAE})$
is solvable in polynomial time and in particular it is solved by the so-called
affine integer programming relaxation ($\operatorname{AIP}$), whose power was
characterised in [6].

More generally, one fixes two relational structures $\mathbf{A}$ and
$\mathbf{B}$ with $\mathbf{A}\to\mathbf{B}$. The
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is then, in the decision version,
the computational problem of distinguishing (input) relational structures
$\mathbf{X}$ with $\mathbf{X}\to\mathbf{A}$ from those with
$\mathbf{X}\not\to\mathbf{B}$. In the search version,
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is the problem of finding a
homomorphism from an input structure $\mathbf{X}$ to $\mathbf{B}$ given that
one is promised that $\mathbf{X}\to\mathbf{A}$. One can think of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ as an approximation version of
$\operatorname{CSP}(\mathbf{A})$ on satisfiable instances. Another way is to
think of $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ as
$\operatorname{CSP}(\mathbf{B})$ with restricted inputs. We refer the reader
to [25] for a very recent survey on PCSPs.

For CSPs, a dichotomy conjecture of Feder and Vardi [19] was resolved
independently by Bulatov [15] and Zhuk [31] via the so-called algebraic
approach [24, 14]: For every fixed finite $\mathbf{A}$,
$\operatorname{CSP}(\mathbf{A})$ is either solvable in polynomial time or
$\operatorname{CSP}(\mathbf{A})$ is NP-complete.

For PCSPs, even the case of graphs and structures on Boolean domains is widely
open; these two were established for CSPs a long time ago [23, 29] and
constituted important evidence for conjecturing a dichotomy. Following the
important work of Barto et al. [6] on extending the algebraic framework from
the realms of CSPs to the world of PCSPs, there have been several recent works
on complexity classifications of fragments of PCSPs [20, 22, 8, 12, 5, 2, 9,
13, 27, 26], hardness conditions [6, 12, 7, 30], and power of algorithms [6,
10, 3, 17]. Nevertheless, a classification of more concrete fragments of PCSPs
is needed for making progress with the general theory, such as finding
hardness and tractability criteria, as well as with resolving longstanding
open questions, such as approximate graph colouring.

Brakensiek and Guruswami classified
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ for all Boolean symmetric
structures $\mathbf{A}$ and $\mathbf{B}$ with disequalities [8]. Ficak, Kozik,
Olšák, and Stankiewicz generalised this result by classifying
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ for all Boolean symmetric
structures $\mathbf{A}$ and $\mathbf{B}$ [20].

Barto, Battistelli, and Berg [5] studied symmetric PCSPs on non-Boolean
domains and in particular PCSPs of the form
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{B})$,
where $\mathbf{B}$ contains a single ternary relation over the domain
$\\{0,1,\ldots,d-1\\}$. For $d=2$, a complete classification
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{B})$
is known [8, 20]. For $d=3$, Barto et al. [5] managed to classify all but one
structure $\mathbf{B}$. The remaining open case of “linearly ordered
colouring” inspired further investigation in [27]. For $d=4$, Barto et al. [5]
obtained partial results. In particular, for certain structures $\mathbf{B}$
they managed to rule out the applicability of the $\operatorname{BLP+AIP}$
algorithm from [10]. The significance of $\operatorname{BLP+AIP}$ here is that
it is the strongest known algorithm for PCSPs for which a characterisation of
its power is known both in terms of a minion and also in terms of polymorphism
identities. This suggests that those cases are NP-hard (or new algorithmic
techniques are needed).

#### Contributions.

We continue the work from [8, 20] and [5] and focus on promise constraint
satisfaction problems of the form
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, where $\mathbf{A}$ is symmetric
and $\mathbf{B}$ is over an arbitrary finite domain.111All structures in this
article can be assumed to be finite unless they are explicitly stated to be
infinite. Since the template $\mathbf{A}$ is symmetric, we can assume without
loss of generality that $\mathbf{B}$ is symmetric, as observed in [5] and in
[13].222In detail, for any symmetric $\mathbf{A}$ and (not necessarily
symmetric) $\mathbf{B}$ with $\mathbf{A}\to\mathbf{B}$, there is a symmetric
$\mathbf{B}^{\prime}$ with $\mathbf{A}\to\mathbf{B}^{\prime}$ such that
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ and
$\operatorname{PCSP}(\mathbf{A},\mathbf{B}^{\prime})$ are polynomial-time
equivalent [5, 13]. This $\mathbf{B}^{\prime}$ is the largest symmetric
substructure of $\mathbf{B}$. Observe that a functional structure has
functional substructures, so if $\mathbf{B}$ is functional then
$\mathbf{B}^{\prime}$ remains functional.

As our main result, we establish the following result. A structure
$\mathbf{B}$ is called _functional_ if, for any relation $R^{\mathbf{B}}$ in
$\mathbf{B}$ of, say, arity $r$, and any tuple $x\in R^{\mathbf{B}}$, any
$r-1$ elements of $x$ determine the last element. In detail,
$(x_{1},\ldots,x_{r-1},y),(x_{1},\ldots,x_{r-1},z)\in R^{\mathbf{B}}$ implies
$y=z$, and similarly for the other $r-1$ positions.333Note that for symmetric
$\mathbf{B}$ the requirement “for the other $r-1$ positions” is satisfied
automatically. The notions of dependency and additivity will be defined in
Section 3: for the moment, consider them simply as technical conditions on
$(\mathbf{A},\mathbf{B})$. Finite tractability is defined in Section 2.

######  Theorem 1.

Let $\mathbf{A}$ be a symmetric structure and $\mathbf{B}$ be a functional
structure such that $\mathbf{A}\to\mathbf{B}$. Assume that
$(\mathbf{A},\mathbf{B})$ is dependent and additive. Then, either
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is solvable in polynomial time by
$\operatorname{AIP}$ and is finitely tractable, or
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is NP-hard.

Our main motivation for studying PCSPs with functional structures is the fact
that more complexity classifications of PCSP fragments are needed to make
progress with the general theory of PCSPs. Furthermore, functional PCSPs
generalise linear equations, an important and fundamental class of CSPs.
Finally, topological methods [26] seem inapplicable to resolving the
computational complexity of functional PCSPs and thus other methods are
required.

Theorem 1 has the following three corollaries. The first corollary applies to
structures $\mathbf{A}$ that are Boolean.

######  Corollary 2.

Let $\mathbf{A}$ be a Boolean symmetric structure and $\mathbf{B}$ be a
functional structure such that $\mathbf{A}\to\mathbf{B}$. Then, either
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is solvable in polynomial time by
$\operatorname{AIP}$ and is finitely tractable, or
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is NP-hard.

The second corollary applies to structures $\mathbf{A}$ consisting of a single
relation of a small arity.

######  Corollary 3.

Let $\mathbf{A}$ be a symmetric structure and $\mathbf{B}$ be a functional
structure such that $\mathbf{A}\to\mathbf{B}$. Assume that both $\mathbf{A}$
and $\mathbf{B}$ have exactly one relation of arity at most 4. Then, either
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is solvable in polynomial time,
or $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is NP-hard.

An example of a Boolean symmetric structure $\mathbf{A}$ is
$\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3}$, and more generally
$\mathbf{q}\textbf{-}\mathbf{in}\textbf{-}\mathbf{r}$.444$\mathbf{q}\textbf{-}\mathbf{in}\textbf{-}\mathbf{r}$
is the structure on $\\{0,1\\}$ with a single (symmetric) relation of arity
$r$ containing all $r$-tuples with precisely $q$ $1$s (and $r-q$ $0$s). The
structure $\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3}$ is not only
Boolean (and thus is captured by Corollary 2) but also consists of a single
relation of arity 3 (and thus is also captured by Corollary 3). In fact, it
satisfies another property, leading to the following generalisation of
$\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3}$, which applies to
structures $\mathbf{A}$ with a certain connectivity property. We will need
some notation. Define $\operatorname{dist}_{R}(x,y)$ as being the distance
between $x$ and $y$ when viewed as vertices in a hypergraph whose edge
relation is $R$. Thus, for instance, $\operatorname{dist}_{R}(x,x)=0$, and if
$x$ and $y$ are in different connected components then
$\operatorname{dist}_{R}(x,y)=\infty$. Define
$\operatorname{diam}(V,E)=\max_{u,v\in V}\operatorname{dist}_{E}(u,v)$.

######  Corollary 4.

Let $\mathbf{A}$ be a symmetric structure and $\mathbf{B}$ be a functional
structure such that $\mathbf{A}\to\mathbf{B}$. Assume that $\mathbf{A}$ has a
relation $R^{\mathbf{A}}$ of arity at least 3 for which
$\operatorname{diam}(A,R^{\mathbf{A}})\leq 1$. Then, either
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is solvable in polynomial time by
$\operatorname{AIP}$ and is finitely tractable, or
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is NP-hard.

A hypergraph is called _linear_ if no two distinct edges intersect in more
than one vertex. We remark that any _linear_ $r$-uniform hypergraph can be
seen as a functional symmetric relational structure with one $r$-ary relation.

Several researchers have informally conjectured that
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{B})$
admits a dichotomy. The authors, as well as other researchers, believe that in
fact not only is there a dichotomy but also all tractable cases are solvable
by $\operatorname{AIP}$ (cf. also Remark 39).

######  Conjecture 5.

For every structure $\mathbf{B}$, either
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{B})$
is solvable in polynomial time by $\operatorname{AIP}$, or
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is NP-hard.

Theorem 1 establishes the special case of Conjecture 5 for functional
$\mathbf{B}$. We make further progress towards Conjecture 5 by proving that
for any structure $\mathbf{A}$ with a single _(not necessarily Boolean)_
symmetric relation, and any _(not necessarily functional)_ structure
$\mathbf{B}$ for which $\mathbf{A}\to\mathbf{B}$, $\operatorname{BLP+AIP}$
from [10] is no more powerful for $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$
than $\operatorname{AIP}$ from [8], although in general
$\operatorname{BLP+AIP}$ is strictly stronger than $\operatorname{AIP}$ [10],
already for (non-promise) $\operatorname{CSP}$s with _two_ Boolean symmetric
relations, cf. Remark 57. In fact, we establish a more general result. We say
that a relation $R$ is _balanced_ if there exists a matrix $M$ whose columns
are tuples of $R$, where each tuple of $R$ appears as a column (possibly a
multiple times), and where the rows of $M$ are permutations of each other. The
matrix $M$ below shows that the Boolean
$\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3}$ relation is balanced:

$M=\begin{pmatrix}1&0&0\\\ 0&1&0\\\ 0&0&1\\\ \end{pmatrix}.$

######  Theorem 6.

Let $\mathbf{A}$ be any structure with a single relation. If the relation in
$\mathbf{A}$ is balanced then, for any $\mathbf{B}$ such that
$\mathbf{A}\to\mathbf{B}$, $\operatorname{BLP+AIP}$ solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if and only if
$\operatorname{AIP}$ solves it.

If the (only) relation in $\mathbf{A}$ is _binary_ (i.e., a digraph), the
condition of balancedness has a natural combinatorial interpretation: A binary
relation is balanced if and only if it is the disjoint union of strongly
connected components (cf. Appendix A).

Theorem 6 implies the following corollary. We say that a relation of arity $r$
is _preserved_ by a group of permutations of degree $r$ if and only if
permuting any tuple of the relation according to any permutation of the group
gives another tuple of the relation.

######  Corollary 7.

Suppose that $G$ is a transitive group of permutations. Further, suppose that
$\mathbf{A}$ is a relational structure with one relation that is preserved by
$G$. Then, for any $\mathbf{A}\to\mathbf{B}$, $\operatorname{BLP+AIP}$ solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if and only if
$\operatorname{AIP}$ does.

While Corollary 7 is more elegant than Theorem 6, it applies to fewer
structures. Indeed, we will show in Remark 60 that there exist balanced
relations that are not preserved by any transitive group. Examples of
relations that are preserved by some transitive group of permutations $G$
include symmetric relations (where $G$ is the symmetric group) or cyclic
relations (where $G$ contains all cyclic shifts of appropriate degree).

##  2 Preliminaries

We let $[r]=\\{1,\ldots,r\\}$. We denote by $2^{S}$ the powerset of $S$.

#### Structures and PCSPs

Promise CSPs have been introduced in [4] and [8]. We follow the notation and
terminology of [6].

A (relational) _structure_ is a tuple
$\mathbf{A}=(A;R_{1}^{\mathbf{A}},\ldots,R_{t}^{\mathbf{A}})$, where
$R_{i}^{\mathbf{A}}\subseteq A^{\operatorname{ar}(R_{i})}$ is a relation of
arity $\operatorname{ar}(R_{i})$ on a set $A$, called the _domain_. A
structure $\mathbf{A}$ is called _Boolean_ if $A=\\{0,1\\}$ and is called
_symmetric_ if $R_{i}^{\mathbf{A}}$ is a symmetric relation for each
$i\in[t]$; i.e, if $(x_{1},\ldots,x_{\operatorname{ar}(R_{i})})\in
R_{i}^{\mathbf{A}}$ then for every permutation $\pi$ on
$[\operatorname{ar}(R_{i})]$ we have
$(x_{\pi(1)},\ldots,x_{\pi(\operatorname{ar}(R_{i}))})\in R_{i}^{\mathbf{A}}$.
A structure $\mathbf{A}$ is called _functional_ if
$(x_{1},\ldots,x_{\operatorname{ar}(R_{i})-1},y)\in R_{i}^{\mathbf{A}}$ and
$(x_{1},\ldots,x_{\operatorname{ar}(R_{i})-1},z)\in R_{i}^{\mathbf{A}}$
implies $y=z$ for any $i\in[t]$, and that the same hold for all other $r-1$
positions in the tuple. For any $r$-ary functional relation $R\subseteq
A^{r}$, we define a partial map also called $R$ from $A^{r-1}$ to $A$ in the
following way: for any $x_{1},\ldots,x_{r-1}\in A$, $R(x_{1},\ldots,x_{r-1})$
is the unique value $y$ such that $(x_{1},\ldots,x_{r-1},y)\in R$, if it
exists; $R(x_{1},\ldots,x_{r-1})$ is undefined if no such value exists.

For two structures
$\mathbf{A}=(A;R_{1}^{\mathbf{A}},\ldots,R_{t}^{\mathbf{A}})$ and
$\mathbf{B}=(B;R_{1}^{\mathbf{B}},\ldots,R_{t}^{\mathbf{B}})$ with $t$
relations with the same arities, a _homomorphism from $\mathbf{A}$ to
$\mathbf{B}$_ is a function $h:A\to B$ such that, for any $i\in[t]$, for each
$x=(x_{1},\ldots,x_{\operatorname{ar}(R_{i})})\in R_{i}^{\mathbf{A}}$, we have
$h(x)=(h(x_{1}),\ldots,h(x_{\operatorname{ar}(R_{i})}))\in
R_{i}^{\mathbf{B}}$. We denote the existence of a homomorphism from
$\mathbf{A}$ to $\mathbf{B}$ by $\mathbf{A}\to\mathbf{B}$.

Let $\mathbf{A}$ and $\mathbf{B}$ be two structures with
$\mathbf{A}\to\mathbf{B}$; we call $(\mathbf{A},\mathbf{B})$ a (PCSP)
_template_. In the _search_ version of the _promise constraint satisfaction
problem_ (PCSP) with the template $(\mathbf{A},\mathbf{B})$, denoted by
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, the task is: Given a structure
$\mathbf{X}$ with the promise that $\mathbf{X}\to\mathbf{A}$, find a
homomorphism from $\mathbf{X}$ to $\mathbf{B}$ (which necessarily exists as
homomorphisms compose). In the _decision_ version of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, the task is: Given a structure
$\mathbf{X}$, output Yes if $\mathbf{X}\to\mathbf{A}$, and output No if
$\mathbf{X}\not\to\mathbf{B}$. The decision version trivially reduces to the
search version. We will use the decision version in this paper.

We will be interested in the complexity of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B}$), in particular for symmetric
$\mathbf{A}$ and functional $\mathbf{B}$. (As discussed in Section 1, the
symmetricity of $\mathbf{A}$ means that we can without loss of generality
assume symmetricity of $\mathbf{B}$.)

#### Operations and polymorphisms

A function $h:A^{n}\to B$ is called an _operation_ of arity $n$. A
$(2n+1)$-ary operation $f:A^{2n+1}\to B$ is called _$2$ -block-symmetric_ if
$f(a_{1},\ldots,a_{2n+1})=f(a_{\pi(1)},\ldots,\allowbreak a_{\pi(2n+1)})$ for
every $a_{1},\ldots,a_{2n+1}\in A$ and every permutation $\pi$ on $[2n+1]$
that preserves parity; i.e, $\pi$ maps odd values to odd values and even
values to even values.

A $(2n+1)$-ary operation $f:A^{2n+1}\to B$ is called _alternating_ if it is
2-block-symmetric, and furthermore
$f(a_{1},\ldots,a_{2n-1},a,a)=f(a_{1},\ldots,a_{2n-1},a^{\prime},a^{\prime})$
for every $a_{1},\ldots,a_{2n-1},a,a^{\prime}\in A$.

Consider structures $\mathbf{A},\mathbf{B}$ with $t$ relations with the same
arities. We call $h:A^{n}\to B$ a _polymorphism_ of $(\mathbf{A},\mathbf{B})$
if the following holds for any relation $R=R_{i}$, $i\in[t]$, or arity
$r=\operatorname{ar}(R)$. For any $x^{1},\ldots,x^{r}\in A^{n}$, where
$x^{i}=(x_{1}^{i},\ldots,x_{n}^{i})$, with $(x^{1}_{i},\ldots,x^{r}_{i})\in
R^{\mathbf{A}}$ for every $1\leq i\leq n$, we have
$(h(x^{1}),\ldots,h(x^{r}))\in R^{\mathbf{B}}$. One can visualise this as an
$(r\times n)$ matrix whose rows are the tuples $x^{1},\ldots,x^{r}$. The
requirement is that if every column of the matrix is in $R^{\mathbf{A}}$ then
the application of $h$ on the rows of the matrix results in a tuple from
$R^{\mathbf{B}}$. We denote by
$\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$ the set of $n$-ary
polymorphisms of $(\mathbf{A},\mathbf{B})$ and by
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ the set of all polymorphisms of
$(\mathbf{A},\mathbf{B})$.

#### Relaxations

There are two standard polynomial-time solvable relaxations for PCSPs, the
_basic linear programming_ relaxation ($\operatorname{BLP}$) and the _affine
integer programming_ relaxation ($\operatorname{AIP}$) [8]. The
$\operatorname{AIP}$ solves most tractable PCSPs studies in this paper, with
the exception of cases covered in Corollary 3 (cf. also Remark 39). There is
also a combination of the two, called $\operatorname{BLP+AIP}$ [10], that is
provably stronger than both $\operatorname{BLP}$ and $\operatorname{AIP}$. We
will show that for certain PCSPs, this is not the case (cf. Theorem 6). The
precise definitions of the relaxations are not important for us as we will
only need the notion of solvability of PCSPs by these relaxations and
characterisations of the power of the relaxations; we refer the reader to [8,
6, 10] for details. Let $\mathbf{X}$ be an instance of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$. It follows from the definitions
of the relaxations that if $\mathbf{X}\to\mathbf{A}$ then both
$\operatorname{AIP}$ and $\operatorname{BLP+AIP}$ accept [8, 6]. We say that
$\operatorname{AIP}$ ($\operatorname{BLP+AIP}$, respectively) _solves_
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if, for every $\mathbf{X}$ with
$\mathbf{X}\not\to\mathbf{B}$, $\operatorname{AIP}$ ($\operatorname{BLP+AIP}$,
respectively) rejects.

The power of $\operatorname{AIP}$ and $\operatorname{BLP+AIP}$ for PCSPs is
characterised by the following results.

######  Theorem 8 ([6]).

$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is solved by $\operatorname{AIP}$
if and only if $\operatorname{Pol}(\mathbf{A},\mathbf{B})$ contains
alternating operations of all odd arities.

######  Theorem 9 ([10]).

$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is solved
$\operatorname{BLP+AIP}$ if and only if
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ contains 2-block-symmetric
operations of all odd arities.

We now define the notion of _finite tractability_ [6, 2]. We say that
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is finitely tractable if
$\mathbf{A}\to\mathbf{E}\to\mathbf{B}$ for some finite structure $\mathbf{E}$
and $\operatorname{CSP}(\mathbf{E})$ is tractable. For a group $G$, we use the
standard notation $H\lhd G$ to indicate that $H$ is a normal subgroup of $G$.

######  Lemma 10.

Suppose $\mathbf{A}\to\mathbf{E}\to\mathbf{B}$, where $E=G$ for some Abelian
group $(G,+)$, and each relation of $\mathbf{E}$ is either of the form (i)
$c+H$ for some $r\in\mathbb{N}$, $c\in G^{r}$ and $H\lhd G^{r}$, or (ii)
empty. Then, $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is solvable in
polynomial time by $\operatorname{AIP}$ and is finitely tractable.

###### Proof.

The following alternating operation is a polymorphism of $\mathbf{E}$

$f(x_{1},y_{1},\ldots,y_{k},x_{k+1})=\sum_{i=1}^{k+1}x_{i}-\sum_{i=1}^{k}y_{i}.$

Consider a relation $R^{\mathbf{E}}$ of $\mathbf{E}$, of the form $c+H$.
Consider a matrix of inputs whose columns are
$x_{1},y_{1},\ldots,y_{k},x_{k+1}\in R^{\mathbf{E}}$. In other words,
$x_{i}\in c+H$ and $y_{i}\in c+H$ for each $x_{i},y_{i}$. Note that the column
that results from applying $f$ to the rows of this matrix is just

$x_{1}-y_{1}+\cdots-y_{k}+x_{k+1}\in(c+H)-(c+H)+\cdots-(c+H)+(c+H)\subseteq
c+H$

Thus $f$ is an alternating polymorphism of $\mathbf{E}$. It follows that
$\operatorname{CSP}(\mathbf{E})$ is solved by $\operatorname{AIP}$, from
whence it follows that $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is
finitely tractable and solved by $\operatorname{AIP}$. ∎

#### Minions

We will use the theory of minions from [6]. Let $\mathcal{M}$ be a set, where
each element $f\in\mathcal{M}$ is assigned an arity $\operatorname{ar}(f)$. We
write $\mathcal{M}^{(n)}=\\{f\in\mathcal{M}\mid\operatorname{ar}(f)=n\\}$.
Further, let $\mathcal{M}$ be endowed with, for each $\pi:[n]\to[m]$, a (so-
called minor) map $f\mapsto f^{\pi}:\mathcal{M}^{(n)}\to\mathcal{M}^{(m)}$
such that, for $\pi:[m]\to[k]$ and $\sigma:[n]\to[m]$, and any
$f\in\mathcal{M}^{(n)}$ we have ${(f^{\pi})}^{\sigma}=f^{\sigma\circ\pi}$, and
$f^{\textrm{id}}=f$. Then, $\mathcal{M}$ is called a _minion_.555A minion is a
functor from the skeleton of the category of finite sets to the category of
sets. We often write $f\xrightarrow{\pi}g$ instead of $g=f^{\pi}$.

Consider two minions $\mathcal{M},\mathcal{N}$; a _minion homomorphism_ is a
map $\xi:\mathcal{M}\to\mathcal{N}$ such that, for any $f\in\mathcal{M}^{(n)}$
and $\pi:[n]\to[m]$, we have that ${\xi(f)}^{\pi}=\xi(f^{\pi})$.666Minion
homomorphisms are natural transformations. If such a minion homomorphism
exists, we write $\mathcal{M}\to\mathcal{N}$.

Given an $n$-ary operation $f:A^{n}\to B$ and a map $\pi:[n]\to[m]$, an
$m$-ary operation $g:A^{m}\to B$ is called a _minor_ of $f$ given by the map
$\pi$ if

$g(x_{1},\ldots,x_{m})=f(x_{\pi(1)},\ldots,x_{\pi(n)}).$

The polymorphisms $\operatorname{Pol}(\mathbf{A},\mathbf{B})$ thus form a
minion, where $f^{\pi}$ is given by the minor of $f$ at $\pi$.

The main hardness theorem that we will use is the following.777In [6], this is
Theorem 5.21 together with Lemma 5.11, as detailed after the proof of Theorem
5.21 therein.

######  Theorem 11 ([6]).

Fix constants $m$ and $C$. Take any template $(\mathbf{A},\mathbf{B})$ such
that
$\operatorname{Pol}(\mathbf{A},\mathbf{B})=\bigcup_{i=1}^{m}\mathcal{M}_{i}$
is the union of $m$ parts. Suppose that for each $i\in[m]$ there exists a map
$I_{i}$ that takes $f\in\mathcal{M}_{i}$ to a subset of
$[\operatorname{ar}(f)]$ of size at most $C$ such that the following holds:
for any $f,g\in\mathcal{M}_{i}$ such that $g=f^{\pi}$ we have that
$I_{i}(g)\cap\pi(I_{i}(f))\neq\emptyset$. Then,
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is NP-hard.

##  3 Additivity and dependency

In this section we will define two new concepts for a template
$(\mathbf{A},\mathbf{B})$, additivity and dependency. Let
$f\in\operatorname{Pol}(\mathbf{A},\mathbf{B})$ be a polymorphism of
$(\mathbf{A},\mathbf{B})$. Intuitively, additivity constrains the value of $f$
evaluated at two elements and dependency ensures that $f$ is determined by
such evaluations. The end goal of this section is to prove the following two
theorems.

######  Theorem 12.

Suppose $\mathbf{A}$ has a relation $R^{\mathbf{A}}$ of arity at least 3 for
which $\operatorname{diam}(A,R^{\mathbf{A}})\leq 1$. Then, for any functional
$\mathbf{B}$ such that $\mathbf{A}\to\mathbf{B}$, $(\mathbf{A},\mathbf{B})$ is
additive and dependent.

######  Theorem 13.

Suppose $\mathbf{A}$ has a relation $R^{\mathbf{A}}$ of arity 3 or 4 that is
connected when viewed as the edge relation of a hypergraph on vertices $A$.
Then, for any functional $\mathbf{B}$ such that $\mathbf{A}\to\mathbf{B}$,
$(\mathbf{A},\mathbf{B})$ is additive and dependent.

###  3.1 Additivity

Fix a polymorphism $f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$. For
any $(i,j)\in A^{2}$ (including the case where $i=j$), we can define a
function $f_{ij}$ derived from $f$ in the following way: $f_{ij}:2^{[n]}\to B$
is a function where

$f_{ij}(S)=f(x_{1},\ldots,x_{n})$

where $x_{k}=j$ if $k\in S$ and $x_{k}=i$ otherwise. In other words,
$f_{ij}(S)$ is $f$ evaluated at the characteristic vector of $S$, where $j$
indicates membership in $S$ and $i$ indicates non-membership.

We define $f^{p}:2^{[n]}\to B^{A^{2}}$ to be the function

$f^{p}(S)(i,j)=f_{ij}(S).$

We will be interested in templates $(\mathbf{A},\mathbf{B})$ that have the
following property.

######  Definition 14.

Fix a template $(\mathbf{A},\mathbf{B})$ with $\mathbf{A}$ symmetric and
$\mathbf{B}$ functional. We say that $(\mathbf{A},\mathbf{B})$ is _additive_
if there exists an operator $+:B^{A^{2}}\times B^{A^{2}}\to B^{A^{2}}$ such
that, for any $f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$ and
disjoint $S,T\subseteq[n]$ we have

$f^{p}(S)+f^{p}(T)=f^{p}(S\cup T).$

######  Lemma 15.

If $(\mathbf{A},\mathbf{B})$ is additive, there exists an operator
$-:B^{A^{2}}\times B^{A^{2}}\to B^{A^{2}}$ such that, for any
$f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$ and $S\subseteq
T\subseteq[n]$, we have

$f^{p}(T)-f^{p}(S)=f^{p}(T\setminus S).$

###### Proof.

While $f^{p}(S)$ has been written as a function from $A^{2}$ to $B$ above, we
can also see it as an $|A|\times|A|$ matrix of elements of $B$. Thus we can
take the transpose of this matrix, denoted by the superscript $T$ below.
Observe that
${(f^{p}(S))}^{T}(i,j)=f_{ji}(S)=f_{ij}(\overline{S})=f^{p}(\overline{S})(i,j)$,
where $\overline{S}$ denotes the complement of $S$. In other words,
${(f^{p}(S))}^{T}=f^{p}(\overline{S})$.

Set $x-y={(x^{T}+y)}^{T}$. Then for $S\subseteq T\subseteq[n]$,

$f^{p}(T)-f^{p}(S)={({f^{p}(T)}^{T}+f^{p}(S))}^{T}=f^{p}(\overline{\overline{T}\cup
S})=f^{p}(T\setminus S).\qed$

######  Lemma 16.

Suppose $(\mathbf{A},\mathbf{B})$ is additive. Fix a polymorphism
$f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$. Consider any family of
disjoint sets $\mathcal{A}\subseteq 2^{[n]}$, containing at least
$|B|^{|A|^{2}}$ sets. Then some nonempty subset
$\mathcal{B}\subseteq\mathcal{A}$ exists such that
$f^{p}(\bigcup\mathcal{B})=f^{p}(\emptyset)$.

The approach used to prove this is analogous to the following well known
exercise (first set out by Vázsonyi and Sved, according to Erdös [1]): Prove
that any sequence of $n$ integers has a subsequence whose sum is divisible by
$n$.

###### Proof.

Note that $\mathcal{A}$ contains at least
$|B|^{|A|^{2}}\geq|\operatorname{range}(f^{p})|$ different sets. Let
$A_{1},\ldots,A_{|\operatorname{range}(f^{p})|}$ be some of these sets. Define
$B_{i}=\bigcup_{j\leq i}A_{j}$ for $0\leq i\leq|\operatorname{range}(f^{p})|$;
note that $B_{0}=\emptyset$. By the pigeonhole principle there exists $0\leq
i<j\leq|\operatorname{range}(f^{p})|$ such that $f^{p}(B_{i})=f^{p}(B_{j})$.
Then, using Lemma 15, $f^{p}(B_{j}\setminus
B_{i})=f^{p}(B_{j})-f^{p}(B_{i})=f^{p}(B_{i})-f^{p}(B_{i})=f^{p}(B_{i}\setminus
B_{i})=f^{p}(\emptyset)$. Thus $\mathcal{B}=\\{A_{i+1},\ldots,A_{j}\\}$ is the
required family of sets. ∎

######  Lemma 17.

Suppose $(\mathbf{A},\mathbf{B})$ is additive. Fix a polymorphism
$f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$. Consider any
$S\subseteq[n]$. There exists $T\subseteq S$ of size at most $|B|^{|A|^{2}}$
such that $f^{p}(S)=f^{p}(T)$.

###### Proof.

Suppose this is not the case, and suppose that $S$ is a minimal counterexample
(with respect to inclusion) to this claim. Clearly $|S|>|B|^{|A|^{2}}$, or
else taking $T=S$ shows that $S$ is no counterexample at all. Thus, apply
Lemma 16 to the family $\\{\\{x\\}\mid x\in S\\}$ to find that some nonempty
subset $U\subseteq S$ exists such that $f^{p}(U)=f^{p}(\emptyset)$. But now,
take $S^{\prime}=S\setminus U\subseteq S$, and note that
$f^{p}(S^{\prime})=f^{p}(S\setminus
U)=f^{p}(S)-f^{p}(U)=f^{p}(S)-f^{p}(\emptyset)=f^{p}(S\setminus\emptyset)=f^{p}(S)$.
By the minimality of $S$, $S^{\prime}$ has a subset $T$ of size at most
$|B|^{|A|^{2}}$ such that $f^{p}(T)=f^{p}(S^{\prime})=f^{p}(S)$, which
contradicts the fact that $S$ is a counterexample. ∎

###  3.2 Dependency

Fix again a polymorphism
$f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$.

######  Definition 18.

We call $(\mathbf{A},\mathbf{B})$ _dependent_ if there exists a map $h$ such
that, for every $f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$, we have
that

$f(x_{1},\ldots,x_{n})=h(f(\alpha(x_{1}),\ldots,\alpha(x_{n}))\mid\alpha:A\to
S,S\in A^{\leq 2}),$

where $A^{\leq 2}$ is the set of nonempty subsets of $A$ of size at most 2.

Any polymorphism $f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$ is just
a function $f:A^{n}\to B$. Without loss of generality, identify $A$ with the
set $[a]$ from now on. Note that a tuple from $A^{n}={[a]}^{n}$ can be seen as
a partition of $[n]$ into $a$ parts $S_{1},\ldots,S_{a}$: $S_{i}$ is the set
of coordinates in the tuple set to $i$. We will thus denote by $a^{[n]}$ both
the set tuples and the set of such partitions. Thus we can, for example,
evaluate $f$ at a partition $S_{1},\ldots,S_{a}$ of $[n]$ and get
$f(S_{1},\ldots,S_{a})$.

######  Definition 19.

For any polymorphism $f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$, we
define $f^{\star}:a^{[n]}\to{(B^{A^{2}})}^{a}$ by

$f^{\star}(S_{1},\ldots,S_{a})=(f^{p}(S_{1}),\ldots,f^{p}(S_{a})).$

The usefulness of all the concepts introduced so far comes from the following
fact.

######  Lemma 20.

Suppose $(\mathbf{A},\mathbf{B})$ is dependent and additive. Then there exists
a function $h:{(B^{A^{2}})}^{a}\to B$ such that for any polymorphism
$f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$, we have $f=h\circ
f^{\star}$.

In the proof we will freely mix the two notations for functions of form
${[a]}^{n}\to B$. If the input to such functions is written with capital
letters it uses the “families of disjoint sets” notation, and if it is written
with lower case letters it uses the tuple notation.

###### Proof.

We claim that there exists a map $h^{\prime}$ that does not depend on $f$ such
that $h^{\prime}(f^{\star}(x))$ contains all the values $f(\alpha(x))$ for
$\alpha:A\to S$ and $S\in A^{\leq 2}$. If this is the case, then by the
dependency of $(\mathbf{A},\mathbf{B})$ there exists a map $h^{\prime\prime}$
such that $f=h^{\prime\prime}\circ h^{\prime}\circ f^{\star}$, which implies
our conclusion.

Showing that such an $h^{\prime}$ exists is the same as showing that we can
deduce $f(\alpha(x))$ for $\alpha:A\to S,S\in A^{\leq 2}$ from just the values
of $f^{\star}(x)$, in a manner independent of $f$. First, if $S=\\{s\\}$ then
we want to find $f(s,\ldots,s)$. But this value is just $f_{ss}(X)$ for any
$X$, and thus is included in every $f^{p}(S_{i})$ that is within
$f^{\star}(x)$.

Now suppose $S=\\{b,c\\}$, and that $A=B\cup C$ such that $\alpha$ maps $B$ to
$b$ and $C$ to $c$. In this case we observe that $\alpha(x)$ contains a $c$ at
all places where $x$ contained an element in $C$, and contains a $b$
elsewhere. Suppose $S_{1},\ldots,S_{a}$ are sets such that $S_{i}$ contains
all the indices where $x$ is equal to $i$. Thus,
$f(\alpha(x))=f_{bc}\left(\bigcup_{i\in C}S_{i}\right)$. This value is an
element of the tuple $f^{p}\left(\bigcup_{i\in C}S_{i}\right)$, so it is
sufficient to show that we can deduce this latter value from
$f^{\star}(x)=f^{\star}(S_{1},\ldots,S_{a})$. But

$f^{p}\left(\bigcup_{i\in C}S_{i}\right)=\sum_{i\in C}f^{p}(S_{i}).$

All of the elements within this sum are contained within
$f^{\star}(S_{1},\ldots,S_{a})=(f^{p}(S_{1}),\ldots,f^{p}(S_{a}))$. Thus we
can deduce the value of $f(\alpha(x))$ uniquely from $f^{\star}(x)$, without
reference to $f$, as required. ∎

###  3.3 Formal system

We will now describe a system of formal proofs that will help us reason about
additivity and dependency. First we define the semantics of this system.

######  Definition 21.

Suppose $S\subseteq A^{n}$ is a set of $n$-ary tuples, and $t\in A^{n}$ is an
$n$-tuple. We write $S\vDash_{\mathbf{A},\mathbf{B}}t$ (omitting
$\mathbf{A},\mathbf{B}$ if there is no chance for confusion) if there exists a
function $h:B^{S}\to B$ (where we interpret $B^{S}$ as being a tuple indexed
by $S$), such that, for any polymorphism
$f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$, we have that

$f(t)=h(f(u)\mid u\in S).$

In other words, we write $S\vDash t$ if the value of $f(t)$ is uniquely
determined by $f(u)$ for $u\in S$, in a manner independent of $f$.

######  Definition 22.

For any $\mathbf{A}$, we write $\Gamma_{\mathbf{A}}=\\{(r,s,s)\mid s,r\in
A\\}\cup\\{(s,r,s)\mid s,r\in A\\}$ for the set of triples from $A^{3}$ with
the last two elements equal or with the first and last elements equal. Write
$\Delta_{\mathbf{A}}^{n}=\\{(x_{1},\ldots,x_{n})\mid x_{1},\ldots,x_{n}\in
A,|\\{x_{1},\ldots,x_{n}\\}|\leq 2\\}$ i.e. $\Delta_{\mathbf{A}}^{n}$ contains
all the $n$-ary tuples that contain at most two distinct elements.

######  Lemma 23.

$(\mathbf{A},\mathbf{B})$ is additive if for every $p,q\in A$ we have

$\Gamma_{\mathbf{A}}\vDash_{\mathbf{A},\mathbf{B}}(p,p,q).$

###### Proof.

For $p,q\in A$, suppose $h_{qp}$ is the function that witnesses
$\Gamma_{\mathbf{A}}\vDash_{\mathbf{A},\mathbf{B}}(p,p,q)$. Define

$(x+y)(q,p)=h_{qp}(t_{xyz}\mid(x,y,z)\in\Gamma_{\mathbf{A}}),$

where $t_{sss}=x(s,s)$, $t_{rss}=x(s,r)$ and $t_{srs}=y(s,r)$, for $s,r\in A$.
(This defines $t_{xyz}$ for all $(x,y,z)\in\Gamma_{\mathbf{A}}$.)

We claim that this shows the additivity of $(\mathbf{A},\mathbf{B})$. Consider
any polymorphism $f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$ and
disjoint $S,T\subseteq[n]$. Write $\pi:[n]\to[3]$ for the function that takes
$S$ to 1, $T$ to 2, and $[n]\setminus(S\cup T)$ to 3. By the definition of
$h_{qp}$ and that of taking minors, we have

$(f^{p}(S\cup T))(q,p)=f_{qp}(S\cup
T)=f^{\pi}(p,p,q)=h_{qp}(f^{\pi}(x,y,z)\mid(x,y,z)\in\Gamma_{\mathbf{A}}).$

Now, let $t_{xyz}=f^{\pi}(x,y,z)$. Observe that
$t_{sss}=f^{\pi}(s,s,s)=f^{p}(S)(ss)$. Also,
$t_{rss}=f^{\pi}(r,s,s)=f^{p}(S)(s,r)$, and
$t_{srs}=f^{\pi}(s,r,s)=f^{p}(T)(s,r)$. Thus we deduce that

$(f^{p}(S\cup
T))(q,p)=h_{qp}(t_{xyz}\mid(x,y,z)\in\Gamma_{\mathbf{A}})=(f^{p}(S)+f^{p}(T))(q,p).$

Thus by Definition 14,

$f^{p}(S\cup T)=f^{p}(S)+f^{p}(T),$

as required. ∎

######  Lemma 24.

Assuming $A=[a]$, $(\mathbf{A},\mathbf{B})$ is dependent if we have

$\Delta_{\mathbf{A}}^{a}\vDash_{\mathbf{A},\mathbf{B}}(1,\ldots,a).$

###### Proof.

Suppose $h$ witnesses that
$\Delta_{\mathbf{A}}^{a}\vDash_{\mathbf{A},\mathbf{B}}(1,\ldots,a)$. Note that
every tuple in $\Delta_{\mathbf{A}}^{a}$ can be seen as a function from $[a]$
to some $S\subseteq A$ for $0<|S|\leq 2$. In other words $h$ takes a tuple of
elements from $B$, indexed by functions $\alpha:A\to S,S\in A^{\leq 2}$. In
other words, we see that for any $a$-ary polymorphism $f$,

$f(1,\ldots,a)=h(f(\alpha(1),\ldots,\alpha(a))\mid\alpha:A\to S,S\in A^{\leq
2}).$

The type of this function (not coincidentally) is exactly the same as the
function that ought to witness the dependency of $(\mathbf{A},\mathbf{B})$;
and indeed, we claim that it does in fact witness this.

In other words, we must show that, for any
$f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$ and
$x_{1},\ldots,x_{n}\in A$ we have that

$f(x_{1},\ldots,x_{n})=h(f(\alpha(x_{1}),\ldots,\alpha(x_{n}))\mid A\to S,S\in
A^{\leq 2}).$

Observe that for any $x_{1},\ldots,x_{n}$, there exists a function
$\pi:[n]\to[a]$ such that $f(x_{1},\ldots,x_{n})=f^{\pi}(1,\ldots,a)$; namely
$\pi(i)=x_{i}$. Furthermore $f^{\pi}$ is an $a$-ary polymorphism; thus

$f(x_{1},\ldots,x_{n})=f^{\pi}(1,\ldots,a)=h(f^{\pi}(\alpha(1),\ldots,\alpha(a))\mid\alpha:A\to
S,S\in A^{\leq 2})\\\ =h(f(\alpha(x_{1}),\ldots,\alpha(x_{n}))\mid A\to S,S\in
A^{\leq 2}),$

as required. ∎

We now move on to a syntactic description of the formal proof system.

######  Definition 25.

Fix some $n\in\mathbb{N}$. Fix also some relation $R^{\mathbf{A}}$ of
$\mathbf{A}$. For sets of $n$-ary tuples $S\subseteq A^{n}$ and $t\in A^{n}$,
we define $S\vdash_{\mathbf{A},R^{\mathbf{A}}}t$ as the minimal relation that
satisfies the following.

  1. 1.

If $S\subseteq T$ and $S\vdash t$ then $T\vdash t$.

  2. 2.

$t\vdash t$.

  3. 3.

If $S\vdash t$ and $t,T\vdash t^{\prime}$ then $S,T\vdash t^{\prime}$.

  4. 4.

If there exists a matrix with $n$ columns and $r$ rows, whose rows are
$t_{1},\ldots,t_{r}$, and whose columns are tuples of $R^{\mathbf{A}}$, then
$t_{2},\ldots,t_{r}\vdash t_{1}$.

We omit $\mathbf{A},R^{\mathbf{A}}$ if they are obvious from context.

######  Remark 26.

Suppose $R^{\mathbf{A}}$ has arity $r$. Any judgement of the form
$S\vdash_{\mathbf{A},R^{\mathbf{A}}}t$ must have a finite proof using the
rules above by minimality. From this proof, we can create a _proof-tree_ where
the vertices are $n$-ary tuples of $A$, the root is $t$, the leaves belong to
$S$, and every non-leaf has $r-1$ children such that if $t_{1}$ is the non-
leaf and $t_{2},\ldots,t_{r}$ are its children, then the matrix whose rows are
$t_{1},\ldots,t_{r}$ has as its columns only tuples of $R^{\mathbf{A}}$. To
create this tree, proceed inductively on the proof, from the conclusion
backwards. The first and second rule do not modify the proof tree. The third
rule corresponds to recursively constructing a subtree. The final rule is the
only one that adds new vertices to the proof tree.

######  Lemma 27.

If $S\vdash_{\mathbf{A},R^{\mathbf{A}}}t$ then
$S\vDash_{\mathbf{A},\mathbf{B}}t$ for any symmetric $\mathbf{A}$ and
functional $\mathbf{B}$.

###### Proof.

By minimality, it is sufficient to show that $\vDash_{\mathbf{A},\mathbf{B}}$
satisfies all the rules satisfied by $\vdash_{\mathbf{A},R^{\mathbf{A}}}$,
which we do now rule-by-rule. For the following assume always that all tuples
are of arity $n$.

  1. 1.

Suppose $S\subseteq T$ and $S\vDash t$. Thus there exists a function
$h:A^{S}\to A$ such that, for any polymorphism
$f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$, we have

$f(t)=h(f(u)\mid u\in S).$

Now, we define the function $h^{\prime}:A^{T}\to A$ as follows:

$h^{\prime}(x_{u}\mid u\in T)=h(x_{u}\mid u\in S).$

In other words, $h^{\prime}$ ignores all inputs in $T\setminus S$ and
otherwise acts like $h$. We claim that $h^{\prime}$ witnesses that $T\vDash
t$: for any polymorphism
$f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$, we have

$f(t)=h(f(u)\mid u\in S)=h^{\prime}(f(u)\mid u\in T).$

  2. 2.

For any tuple $t$, we have $t\vDash t$; indeed, the identity function
$\operatorname{id}_{B}:B\to B$ witnesses this fact.

  3. 3.

Suppose $S\vDash t$ and $t,T\vDash u$, as witnessed by $h:B^{S}\to B$ and
$h^{\prime}:B^{t+T}\to B$. If $t\in T$ then $T\vDash u$ and we have by the
first rule that $S,T\vDash u$ as required; thus suppose $t\not\in T$. We will
thus interpret $h^{\prime}$ as having signature $h^{\prime}:B\to B^{T}\to B$.
With this interpretation, by definition, for any polymorphism
$f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$, we have

$\displaystyle f(t)$ $\displaystyle=h(f(v)\mid v\in S)$ $\displaystyle f(u)$
$\displaystyle=h^{\prime}(f(t))(f(v)\mid v\in T).$

Now define $h^{\prime\prime}:B^{S\cup T}\to B$ in the following way:

$h^{\prime\prime}(x_{v}\mid v\in S\cup T)=h^{\prime}(h(x_{v}\mid v\in
S))(x_{v}\mid v\in T).$

We find that, for any $f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$,

$f(u)=h^{\prime}(f(t))(f(v)\mid v\in T)=h^{\prime}(h(f(v)\mid v\in
S))(f(v)\mid v\in T)=h^{\prime\prime}(f(v)\mid v\in S\cup T).$

Thus we find that $S,T\vDash u$, as required.

  4. 4.

Suppose $R^{\mathbf{A}}$ has arity $r$, and suppose there exists a matrix with
$n$ columns and $r$ rows, whose rows are $t_{1},\ldots,t_{r}$, and whose
columns are tuples of $R^{\mathbf{A}}$. Let $h:B^{\\{t_{2},\ldots,t^{r}\\}}\to
B$ be defined as follows, interpreting an element of
$B^{\\{t_{2},\ldots,t_{r}\\}}$ as an $(r-1)$-ary tuple in the natural way:

$h(x_{2},\ldots,x_{r})=R^{\mathbf{B}}(x_{2},\ldots,x^{r}).$

Now, we claim that $h$ witnesses that $t_{2},\ldots,t_{r}\vDash t_{1}$.
Indeed, for any $n$-ary polymorphism
$f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$, we have that
$(f(t_{1}),\ldots,f(t_{r}))\in R^{\mathbf{B}}$, and thus

$f(t_{1})=R^{\mathbf{B}}(f(t_{2}),\ldots,f(t_{r}))=h(f(t_{2}),\ldots,f(t_{r}))=h(f(u)\mid
u\in\\{t_{2},\ldots,t_{r}\\}).$

Thus we conclude that $\vDash_{\mathbf{A},\mathbf{B}}$ satisfies the rules of
$\vdash_{\mathbf{A},R^{\mathbf{A}}}$, which implies our conclusion. ∎

######  Lemma 28.

Suppose that $S\vdash_{\mathbf{A},R^{\mathbf{A}}}t$ and
$x\in\operatorname{supp}(R^{\mathbf{A}})$. Then
$S\times\operatorname{supp}(R^{\mathbf{A}})\vdash_{\mathbf{A},R^{\mathbf{A}}}(t,x)$.888Here,
if $t=(t_{1},\ldots,t_{r})$ then $(t,x)=(t_{1},\ldots,t_{r},x)$, and likewise
$S\times\operatorname{supp}(R^{\mathbf{A}})=\\{(s_{1},\ldots,s_{r},x)\mid(s_{1},\ldots,s_{r})\in
S,x\in\operatorname{supp}(R^{\mathbf{A}})\\}$.

###### Proof.

We show this by induction on the formal proof that proves that
$S\vdash_{\mathbf{A},R^{\mathbf{A}}}t$. Based on the last step in the proof
used to prove this fact, we have the following cases.

  1. 1.

Suppose $S^{\prime}\subseteq S$ and $S^{\prime}\vdash t$. By the inductive
hypothesis, we know that that
$S^{\prime}\times\operatorname{supp}(R^{\mathbf{A}})\vdash(t,x)$. As
$S^{\prime}\times\operatorname{supp}(R^{\mathbf{A}})\subseteq
S\times\operatorname{supp}(R^{\mathbf{A}})$, then
$S\times\operatorname{supp}(R^{\mathbf{A}})\vdash(t,x)$ as required.

  2. 2.

Suppose $S=\\{t\\}$. In this case the result is immediate, as
$S\times\operatorname{supp}(R^{\mathbf{A}})\supseteq\\{(t,u)\\}\vdash(t,u)$.

  3. 3.

Suppose $S=X\cup Y$, $X\vdash s$ and $s,Y\vdash t$. By the inductive
hypothesis, for $y\in\operatorname{supp}(R^{\mathbf{A}})$,
$X\times\operatorname{supp}(R^{\mathbf{A}})\vdash(s,y)$ and $\\{(s,y)\mid
y\in\operatorname{supp}(R^{\mathbf{A}})\\},Y\times\operatorname{supp}(R^{\mathbf{A}})\vdash(t,x)$.
We can therefore deduce, by this rule applied
$|\operatorname{supp}(R^{\mathbf{A}})|$ times, that
$S\times\operatorname{supp}(R^{\mathbf{A}})=(X\cup
Y)\times\operatorname{supp}(R^{\mathbf{A}})\vdash(t,x)$.

  4. 4.

Suppose that $S=\\{t_{2},\ldots,t_{r}\\}$ and there exists a matrix whose rows
are $t_{1},\ldots,t_{r}$ and all of whose columns are elements of
$R^{\mathbf{A}}$. Suppose $(x,x_{2},\ldots,x_{r})\in R^{\mathbf{A}}$. Then by
applying this rule we find that $(t_{2},x),\ldots,(t_{r},x_{r})\vdash(t,x)$,
which implies that $S\times\operatorname{supp}(R^{\mathbf{A}})\vdash(t,x)$.

Thus our conclusion follows. ∎

Any tuple $x\in A^{n}$ can be seen as a function from $[n]$ to $A$. Thus for
any function $\pi:[m]\to[n]$, we let $x\circ\pi\in A^{m}$ be the tuple which,
at position $i$, has value $x_{\pi(i)}$. For a set of tuples $S\in A^{n}$, we
let $S\circ\pi=\\{x\circ\pi\mid x\in S\\}$.

######  Lemma 29.

Suppose $S\subseteq A^{n},t\in A^{n}$ and $\pi:[m]\to[n]$. If
$S\vdash_{\mathbf{A},R^{\mathbf{A}}}t$ then
$S\circ\pi\vdash_{\mathbf{A},R^{\mathbf{A}}}t\circ\pi$.

###### Proof.

First, consider any matrix $M$ whose rows are $r_{1},\ldots,r_{n}$ and whose
columns are $c_{1},\ldots,c_{m}$. If we create a matrix $M^{\prime}$ whose
rows are $r_{1}\circ\sigma,\ldots,r_{n}\circ\sigma$ for some
$\sigma:[k]\to[n]$, we observe that the columns of this new matrix are
$c_{\sigma(1)},\ldots,c_{\sigma(k)}$. Thus, the columns of $M^{\prime}$ are a
subset of the columns of $M$.

Consider the proof tree that proves that
$S\vdash_{\mathbf{A},R^{\mathbf{A}}}t$. If a vertex is labeled by a tuple $u$,
transform it into a vertex labeled by $u\circ\pi$. By the previous
observation, this remains a valid proof tree, whose leaves belong to
$S\circ\pi$ and whose root is $t\circ\pi$. Thus $S\circ\pi\vdash t\circ\pi$. ∎

###  3.4 Super-connectedness

Rather than dealing directly with additivity and dependency, we will instead
deal with a notion that implies them.

######  Definition 30.

We say that $\mathbf{A}$ is _super-connected_ if $\mathbf{A}$ has a relation
$R^{\mathbf{A}}$ such that, for every $x,y,z\in A$ (perhaps even with
$|\\{x,y,z\\}|<3$), we have

$\Gamma_{\mathbf{A}}\vdash_{\mathbf{A},R^{\mathbf{A}}}(x,y,z).$

Super-connectedness is a very useful concept: it implies both additivity and
dependency.

######  Lemma 31.

If $\mathbf{A}$ is super-connected then $(\mathbf{A},\mathbf{B})$ is additive
for functional $\mathbf{B}$ where $\mathbf{A}\to\mathbf{B}$.

###### Proof.

An immediate consequence of Lemma 23 and Lemma 27. ∎

######  Lemma 32.

If $\mathbf{A}$ is super-connected then $(\mathbf{A},\mathbf{B})$ is dependent
for functional $\mathbf{B}$ where $\mathbf{A}\to\mathbf{B}$.

We first prove two simple propositions. Assume for them that $\mathbf{A}$ is
super-connected, witnessed by relation $R^{\mathbf{A}}$, and that $|A|>1$.

######  Proposition 33.

$\operatorname{supp}(R^{\mathbf{A}})=A$.

###### Proof.

Suppose for contradiction that this is not the case. Let $x\in
A\setminus\operatorname{supp}(R^{\mathbf{A}})$, and take $y\in A$ such that
$x\neq y$. Now,

$\Gamma_{\mathbf{A}}\vdash_{\mathbf{A},R^{\mathbf{A}}}(x,x,y).$

Consider any proof tree concluding in this judgement. The root vertex cannot
have any children, since no matrix containing $(x,x,y)$ can have its columns
belong to $R^{\mathbf{A}}$, as $x\not\in\operatorname{supp}R^{\mathbf{A}}$.
Thus $(x,x,y)$ is a leaf vertex in the tree, and
$(x,x,y)\in\Gamma_{\mathbf{A}}$. This is not possible, as $x\neq y$. ∎

######  Proposition 34.

$\Delta_{\mathbf{A}}^{n}\vdash(x_{1},\ldots,x_{n})$.

###### Proof.

We prove this fact by induction. We do induction over the lexicographical
ordering on $\\{(n,d)\in\mathbb{N}^{2}\mid n\geq d\\}$. For any
$(n,d)\in\mathbb{N}^{2}$ with $n\geq d$ we prove that
$\Delta_{\mathbf{A}}^{n}\vdash(x_{1},\ldots,x_{n})$ whenever
$|\\{x_{1},\ldots,x_{n}\\}|\leq d$. As our base case, note that the result is
immediate when $n\leq 2$, as $(x_{1},\ldots,x_{n})\in\Delta_{\mathbf{A}}^{n}$
in this case. Thus suppose $n\geq 3$.

First suppose that $x_{1},\ldots,x_{n}$ contains a duplicated pair of values,
say $x_{n-1}=x_{n}$. Now, define $\pi:[n-1]\to[n]$, where $\pi(i)=i$. By the
inductive hypothesis, we know that
$\Delta_{\mathbf{A}}^{n-1}\vdash(x_{1},\ldots,x_{n-1})$. Thus, by Lemma 29,
$\Delta_{\mathbf{A}}^{n-1}\circ\pi\vdash(x_{1},\ldots,x_{n-1})\circ\pi=(x_{1},\ldots,x_{n-1},x_{n-1})=(x_{1},\ldots,x_{n})$.
Furthermore, every tuple of $\Delta_{\mathbf{A}}^{n-1}\circ\pi$ contains at
most 2 values, so it belongs to $\Delta_{\mathbf{A}}^{n}$. Thus in this case
$\Delta_{\mathbf{A}}^{n}\vdash(x_{1},\ldots,x_{n})$.

Now suppose that $x_{1},\ldots,x_{n}$ are all distinct. Since $\mathbf{A}$ is
super-connected, we find that $\Gamma_{\mathbf{A}}\vdash(x_{1},x_{2},x_{3})$.
Thus by Lemma 28, we find that
$\Gamma_{\mathbf{A}}\times{\operatorname{supp}(R^{\mathbf{A}})}^{n-3}\vdash(x_{1},\ldots,x_{n})$.
By Proposition 33, $\operatorname{supp}(R^{\mathbf{A}})=A$, so
$\Gamma_{\mathbf{A}}\times A^{n-3}\vdash(x_{1},\ldots,x_{n})$. But, every
tuple $t\in\Gamma_{\mathbf{A}}\times A^{n-3}$ contains at most $n-1$ distinct
values, so we can apply the inductive hypothesis to them, and find that
$\Delta_{\mathbf{A}}^{n}\vdash t$. Thus
$\Delta_{\mathbf{A}}^{n}\vdash(x_{1},\ldots,x_{n})$, as required. This
completes the proof. ∎

###### Proof of Lemma 32.

$\Delta_{\mathbf{A}}^{a}\vdash(1,\ldots,a)$ by Proposition 34. Thus, by Lemma
27 we have that
$\Delta_{\mathbf{A}}^{a}\vDash_{\mathbf{A},\mathbf{B}}(1,\ldots,a)$, and
therefore dependency follows by Lemma 24. ∎

######  Lemma 35.

Suppose $\mathbf{A}$ has a relation $R^{\mathbf{A}}$ of arity at least 3 for
which $\operatorname{diam}(A,R^{\mathbf{A}})\leq 1$. Then $\mathbf{A}$ is
super-connected.

###### Proof.

Fix $x,y,z\in A$; we must show that $\Gamma_{\mathbf{A}}\vdash(x,y,z)$. We
have several cases.

$\bm{x=z}$ or $\bm{y=z}$.

In this case $(x,y,z)\in\Gamma_{\mathbf{A}}$, so there is nothing left to be
proved.

$\bm{x=y\neq z}$.

In this case $\operatorname{dist}_{R^{\mathbf{A}}}(x,z)=1$, so there exists an
edge $(x,z,a_{3},\ldots,a_{r})\in R^{\mathbf{A}}$. Consider the matrices

$M=\begin{pmatrix}x&x&z\\\ z&a_{3}&x\\\ a_{3}&z&a_{3}\\\ a_{4}&a_{4}&a_{4}\\\
\vdots&\vdots&\vdots\\\ a_{r}&a_{r}&a_{r}\\\ \end{pmatrix},\qquad
N=\begin{pmatrix}z&a_{3}&x\\\ x&z&z\\\ a_{3}&x&a_{3}\\\ a_{4}&a_{4}&a_{4}\\\
\vdots&\vdots&\vdots\\\ a_{r}&a_{r}&a_{r}\\\ \end{pmatrix}.$

Thus we deduce that $(z,a_{3},x),\Gamma_{\mathbf{A}}\vdash(x,x,z)$ and
$\Gamma_{\mathbf{A}}\vdash(z,a_{3},x)$, and thus
$\Gamma_{\mathbf{A}}\vdash(x,x,z)=(x,y,z)$.

$\bm{x\neq y,y\neq z,x\neq z}$.

In this case
$\operatorname{dist}_{R^{\mathbf{A}}}(x,z)=\operatorname{dist}_{R^{\mathbf{A}}}(x,y)=1$,
so there must exist edges
$(x,z,a_{3},\ldots,a_{r}),(x,y,b_{3},\ldots,b_{r})\in R^{\mathbf{A}}$.
Consider the following matrix

$\begin{pmatrix}x&y&z\\\ z&x&x\\\ a_{3}&b_{3}&a_{3}\\\ \vdots&\vdots&\vdots\\\
a_{r}&b_{r}&a_{r}\\\ \end{pmatrix}.$

Thus we find that
$(z,x,x),(a_{3},b_{3},a_{3}),\ldots,(a_{r},b_{r},a_{r})\vdash(x,y,z)$, whence
$\Gamma_{\mathbf{A}}\vdash(x,y,z)$.

Thus our conclusion follows in all cases. ∎

######  Lemma 36.

If $\mathbf{A}$ has a connected relation $R^{\mathbf{A}}$ of arity 3 then
$\mathbf{A}$ is super-connected.

###### Proof.

We see $(A,R^{\mathbf{A}})$ as a connected 3-uniform hypergraph. For $x,y\in
A$ define $\operatorname{dist}(x,y)$ as the distance between $x$ and $y$ in
this hypergraph. We show that
$\Gamma_{\mathbf{A}}\vdash_{\mathbf{A},R^{\mathbf{A}}}(x,y,z)$ for all
$x,y,z\in A$ by induction on
$\min(\operatorname{dist}(x,z),\operatorname{dist}(y,z))$. There are multiple
cases.

$\bm{\operatorname{dist}(x,z)=0}$ or $\bm{\operatorname{dist}(y,z)}=0$.

In this case $(x,y,z)\in\\{(x,y,x),(x,y,y)\\}\subseteq\Gamma_{\mathbf{A}}$, so
there is nothing left to prove.

$\bm{\operatorname{dist}(x,z)=\operatorname{dist}(y,z)=1}$.

In this case, there exists edges $(x,a,z)$, $(y,b,z)$. Now consider the
following matrices:

$M=\begin{pmatrix}x&y&z\\\ z&z&x\\\ a&b&a\end{pmatrix},\qquad
N=\begin{pmatrix}z&z&x\\\ a&x&z\\\ x&a&a\end{pmatrix},\qquad
P=\begin{pmatrix}a&x&z\\\ x&z&x\\\ z&a&a\end{pmatrix}.$

Thus we conclude that $(a,b,a),(z,z,x)\vdash(x,y,z)$,
$(a,x,z),(x,a,a)\vdash(z,z,x)$ and also $(x,z,x),(z,a,a)\vdash(a,x,z)$, from
where the conclusion follows.

$\bm{\operatorname{dist}(x,z)>1}$ or $\bm{\operatorname{dist}(y,z)>1}$.

Without loss of generality suppose $\operatorname{dist}(x,z)>1$. Thus there
exist edges $(x,a,x^{\prime}),(z^{\prime},b,z),(y,c,d)$ such that
$\operatorname{dist}(x^{\prime},z^{\prime})=\operatorname{dist}(x,z)-2$, and
therefore
$\operatorname{dist}(a,z^{\prime}),\operatorname{dist}(b,x)<\operatorname{dist}(x,z)$.
Consider the matrix

$\begin{pmatrix}x&y&z\\\ a&c&z^{\prime}\\\ x^{\prime}&d&b\end{pmatrix}.$

Thus we deduce that $(a,c,z^{\prime}),(x^{\prime},d,b)\vdash(x,y,z)$;
furthermore the inductive hypothesis can be applied to the tuples to the left
of $\vdash$, so this completes the proof in this case.

Thus we find by induction that $\mathbf{A}$ is super-connected. ∎

######  Lemma 37.

If $\mathbf{A}$ has a connected relation $R^{\mathbf{A}}$ of arity 4 then
$\mathbf{A}$ is super-connected.

###### Proof.

We see $(A,R^{\mathbf{A}})$ as a connected 4-uniform hypergraph. For any
$x,y\in\mathbf{A}$, define $\operatorname{dist}(x,y)$ as the distance between
$x$ and $y$ in this hypergraph. We need to show that, for any $x,y,z\in A$, we
have that $\Gamma_{\mathbf{A}}\vdash_{\mathbf{A},R^{\mathbf{A}}}(x,y,z)$. We
show this by induction on
$\operatorname{minmax}(\operatorname{dist}(x,z),\operatorname{dist}(y,z))$
(where $\operatorname{minmax}(a,b)=(\min(a,b),\max(a,b))$), ordered by the
lexicographical ordering. Note that $\Gamma_{\mathbf{A}}$ is symmetric under
swapping its first two elements, as is our inductive variant, and thus our
proposition is thus symmetric in this way in general; thus suppose without
loss of generality that
$\operatorname{dist}(x,z)\leq\operatorname{dist}(y,z)$, and thus that
$\operatorname{minmax}(\operatorname{dist}(x,z),\operatorname{dist}(y,z))=(\operatorname{dist}(x,z),\operatorname{dist}(y,z))$.

$\bm{\operatorname{dist}(x,z)=0}$.

In this case $(x,y,z)=(z,y,z)\in\Gamma_{\mathbf{A}}$, so nothing needs to be
proved.

$\bm{\operatorname{dist}(x,z)=\operatorname{dist}(y,z)=1}$.

In this case, there exist $a,b,c,d$ such that $(x,a,b,z),(y,c,d,z)\in
R^{\mathbf{A}}$. (It may be possible that $a,b,c,d,x,y,z$ are not all
distinct, but this does not change the correctness of the proof that follows.)
Now consider the matrices

$M=\begin{pmatrix}x&y&z\\\ a&c&a\\\ b&d&b\\\ z&z&x\\\ \end{pmatrix},\qquad
N=\begin{pmatrix}z&z&x\\\ b&a&z\\\ a&x&b\\\ x&b&z\end{pmatrix}$

Thus $(a,c,a),(b,d,b),(z,z,x)\vdash(x,y,z)$ i.e.
$(z,z,x),\Gamma_{\mathbf{A}}\vdash(x,y,z)$. Now, by the proof of the previous
lemma since they belong to the tuple $(x,a,b,z)$ of arity at least 3, we find
that $\Gamma_{\mathbf{A}}\vdash(z,z,x)$. Combining these facts we get our
conclusion.

$\bm{\operatorname{dist}(y,z)>\operatorname{dist}(x,z)=1}$.

In this case, there exist edges $(x,a,b,z)$ and $(y,c,d,y^{\prime})$ such that
$\operatorname{dist}(y^{\prime},z)=\operatorname{dist}(y,z)-1$. Furthermore,
there exists an edge $(y^{\prime},f,g,y^{\prime})$ such that

$\operatorname{dist}(f,z),\operatorname{dist}(g,z),\operatorname{dist}(y^{\prime},z)\leq\operatorname{dist}(y^{\prime},z).$

(This second edge s why we must assume $\operatorname{dist}(y,z)>1$, since
this fails for $\operatorname{dist}(y,z)=1$!) Now consider the following two
matrices

$M=\begin{pmatrix}x&y&z\\\ a&c&a\\\ b&d&b\\\ z&y^{\prime}&x\\\
\end{pmatrix},\qquad N=\begin{pmatrix}z&y^{\prime}&x\\\ a&f&a\\\ b&g&b\\\
x&y^{\prime}&z\\\ \end{pmatrix}.$

These matrices show
$(x,y^{\prime},z),(b,g,b),(a,f,a),(b,d,b),(a,c,a)\vdash(x,y,z)$. We can apply
the inductive hypothesis to all the terms on the left of $\vdash$ so we are
done in this case.

$\bm{\operatorname{dist}(y,z)\geq\operatorname{dist}(x,z)>1}$.

In this case there exist edges $(x,a,b,x^{\prime})$, $(z,c,d,z^{\prime})$,
$(y,e,f,y^{\prime})$ and $(y^{\prime},g,h,y^{\prime\prime})$ such that
$\operatorname{dist}(a,z^{\prime})<\operatorname{dist}(x,z)$,
$\operatorname{dist}(x^{\prime},d)<\operatorname{dist}(x,z)$,
$\operatorname{dist}(y^{\prime\prime},z)<\operatorname{dist}(y,z)$. (Namely,
$(x,a,b,x^{\prime})$ is the edge taken from $x$ towards $z$, with $x^{\prime}$
being closer to $z$ than $x$; $(z,c,d,z^{\prime})$ is the edge taken from $z$
to $x$, with $z^{\prime}$ being closer to $x$ than $z$; and
$(y,e,f,y^{\prime})$, $(y^{\prime},g,h,y^{\prime\prime})$ are the edges taken
from $y$ to $z$, with $y^{\prime}$ and $y^{\prime\prime}$ being closer and
closer to $z$ than $y$.) Now consider

$M=\begin{pmatrix}x&y&z\\\ a&e&z^{\prime}\\\ x^{\prime}&f&d\\\
b&y^{\prime}&c\\\ \end{pmatrix},\qquad N=\begin{pmatrix}b&y^{\prime}&c\\\
a&g&z^{\prime}\\\ x&y^{\prime\prime}&z\\\ x^{\prime}&h&d\\\ \end{pmatrix}$

Due to these matrices,
$(a,e,z^{\prime}),(x^{\prime},f,d),(a,g,z^{\prime}),(x,y^{\prime\prime},z),(x^{\prime},y,d)\vdash(x,y,z)$;
by the distance properties mentioned above, we can apply the inductive
hypothesis to all of the tuples on the left of $\vdash$, so
$\Gamma_{\mathbf{A}}\vdash(x,y,z)$.

Thus, by induction, $\Gamma_{\mathbf{A}}\vdash(x,y,z)$ for all $x,y,z\in A$,
which implies our conclusion. ∎

With all of this, we are finally ready to prove Theorem 12 and Theorem 13.

###### Proof of Theorem 12 and Theorem 13.

The structures from Theorem 12 are super-connected by Lemma 35. The structures
from Theorem 13 are super-connected by Lemma 36 and Lemma 37. This is
sufficient for additivity by Lemma 31 and for dependency by Lemma 32. ∎

##  4 Dichotomy

In this section we will prove our main result.

See 1

Before proving Theorem 1, we will prove three interesting corollaries.

See 2

For the proof of Corollary 2, we will need a simple lemma.

######  Lemma 38.

Suppose $\mathbf{A}$ is Boolean, $\mathbf{B}$ is functional, and every
relation of $\mathbf{A}$ is either binary or contains only constant tuples.
Then, $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is solvable in polynomial
time by $\operatorname{AIP}$ and is finitely tractable.

###### Proof.

Consider any $h:\mathbf{A}\to\mathbf{B}$. Suppose $h(0)=h(1)$. Then every
relation in $\mathbf{B}$ contains a constant tuple of the form
$(h(0),\ldots,h(0))$; in this case,
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is trivially solved by
$\operatorname{AIP}$ and is finitely tractable. Thus suppose $h(0)\neq h(1)$.
Any empty relation in $\mathbf{A}$ can be removed (together with the
corresponding relation in $\mathbf{B}$) as it does not affect
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ and the complexity of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$.

Since $\mathbf{B}$ is functional, the binary relations of $\mathbf{A}$ that do
not contain only constant tuples must be the binary disequality. To see why,
consider any relation $R^{\mathbf{A}}$ in $\mathbf{A}$ that contains the tuple
$(0,1)$. $R^{\mathbf{A}}$ cannot contain $(0,0)$ or $(1,1)$, since the
corresponding relation $R^{\mathbf{B}}$ in $\mathbf{B}$ contains $(h(0),h(1))$
and if it contained $(h(0),h(0))$ or $(h(1),h(1))$ it would not be functional.
Since $\mathbf{A}$ is symmetric, $R^{\mathbf{A}}$ also contains the tuple
$(1,0)$. Thus $R^{\mathbf{A}}=\\{(0,1),(1,0)\\}$ is the disequality relation.
It follows that every relation in $\mathbf{A}$ is either a binary disequality,
or consists only of constant tuples. In this case,
$\operatorname{CSP}(\mathbf{A})$ is solved by $\operatorname{AIP}$ and thus
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is solved by $\operatorname{AIP}$
and is finitely tractable. ∎

###### Proof of Corollary 2.

If $\mathbf{A}$ contains only binary relations or relations that contain only
constant tuples, the conclusion follows by Lemma 38. Otherwise, $\mathbf{A}$
has a relation $R^{\mathbf{A}}$ of arity at least 3 with a non-constant tuple
i.e. for which $\operatorname{diam}(A,R^{\mathbf{A}})=1$, and the conclusion
follows from Theorem 1 together with super-connectivity of such structures:
super-connectedness implies additivity (cf. Lemma 31) and dependency (cf.
Lemma 32). ∎

See 3

###### Proof.

First, observe that the conclusion holds trivially if $R^{\mathbf{B}}$ has
arity 1 as in this case $\operatorname{CSP}(\mathbf{B})$ is trivially
tractable. Second, suppose $R^{\mathbf{B}}$ has arity 2. In this case we claim
that $\operatorname{CSP}(\mathbf{B})$ is solvable in polynomial time. Indeed,
an easy modification of the algorithm for 2-colouring will solve this problem.
Thus $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is tractable in this case.

Now, suppose $R^{\mathbf{B}}$ has arity 3 or 4. The conclusion holds for
connected $\mathbf{A}$ by the super-connectedness of structures $\mathbf{A}$
that have a relation of arity 3 or 4 that is connected. Thus suppose that
$\mathbf{A}$ is not connected, and that its connected components are
$\mathbf{A}_{1},\ldots,\mathbf{A}_{k}$ i.e.
$\mathbf{A}=\mathbf{A}_{1}+\cdots+\mathbf{A}_{k}$. If
$\operatorname{PCSP}(\mathbf{A}_{i},\mathbf{B})$ is NP-hard for some $i\in[k]$
then $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ will also be NP-hard (since
there is a trivial reduction from
$\operatorname{PCSP}(\mathbf{A}_{i},\mathbf{B})$ to
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, as
$\mathbf{A}_{i}\to\mathbf{A}$). Thus suppose
$\operatorname{PCSP}(\mathbf{A}_{i},\mathbf{B})$ is solvable in polynomial
time for all $i\in[k]$. Consider any input hypergraph
$\mathbf{X}=\mathbf{X}_{1}+\cdots+\mathbf{X}_{n}$, where
$\mathbf{X}_{1},\ldots,\mathbf{X}_{n}$ are connected. Since the homomorphic
image of a connected hypergraph is connected, if $\mathbf{X}_{i}\to\mathbf{A}$
then $\mathbf{X}_{i}\to\mathbf{A}_{j}$ for some $j\in[k]$. Thus, for the
decision version of $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, it is
sufficient to see if, for all $i\in[n]$ there exists some $j\in[k]$ such that
$\mathbf{X}_{i}$ is a Yes-instance of
$\operatorname{PCSP}(\mathbf{A}_{j},\mathbf{B})$. If so then $\mathbf{X}$ is a
Yes-instance overall. For the search version something similar happens: see if
we can produce a homomorphism $\mathbf{X}_{i}\to\mathbf{B}$ for each
$\mathbf{X}_{i}$ by running the algorithm for
$\operatorname{PCSP}(\mathbf{A}_{j},\mathbf{B})$ for each $\mathbf{A}_{j}$,
and combine these homomorphisms to find a homomorphism
$\mathbf{A}\to\mathbf{B}$. ∎

######  Remark 39.

Unlike in all other results in this paper, solvability by $\operatorname{AIP}$
is not proved in Corollary 3, only polynomial-time solvability. As far as we
know, it well may be that the PCSPs considered in Corollary 3 are not solved
by $\operatorname{AIP}$ (or even $\operatorname{BLP+AIP}$). The way that
tractability is deduced in the proof of Corollary 3 is as follows: If
$\mathbf{A}_{1},\ldots,\mathbf{A}_{k}$ are connected and
$\operatorname{PCSP}(\mathbf{A}_{i},\mathbf{B})$ is tractable, then
$\operatorname{PCSP}(\mathbf{A}_{1}+\cdots+\mathbf{A}_{k},\mathbf{B})$ is
tractable. We give a concrete example of a template with a single symmetric
relation of arity 6 that shows that this reduction _does not_ preserve
solvability by $\operatorname{AIP}$, or even by $\operatorname{BLP+AIP}$. Note
however that Corollary 3 only applies to relations of arity at most 4, so the
corollary might still be strengthened to show solvability by
$\operatorname{AIP}$.

Let $\mathbb{Z}^{\prime}=\\{x^{\prime}\mid x\in\mathbb{Z}\\}$ be a disjoint
copy of $\mathbb{Z}$. Then, let $\mathbf{B}=\mathbf{A}_{1}+\mathbf{A}_{2}$,
where

$\displaystyle\mathbf{A}_{1}$
$\displaystyle=(\\{0,1\\};\\{(x_{1},\ldots,x_{6})\mid x_{1}+\cdots+x_{6}\equiv
1\pmod{2}\\}),$ $\displaystyle\mathbf{A}_{2}$
$\displaystyle=(\\{0^{\prime},1^{\prime},2^{\prime}\\};\\{(x_{1},\ldots,x_{6})\mid
x_{1}+\cdots+x_{6}\equiv 2^{\prime}\pmod{3^{\prime}}\\}).$

Note that $\mathbf{A}_{1},\mathbf{A}_{2},\mathbf{B}$ are all functional and
symmetric. Furthermore, $\operatorname{PCSP}(\mathbf{A}_{1},\mathbf{B})$ and
$\operatorname{PCSP}(\mathbf{A}_{2},\mathbf{B})$ are solved by
$\operatorname{AIP}$ by Theorem 8: a $(2k+1)$-ary alternating polymorphism is

$(x_{1},y_{1},\ldots,x_{k},y_{k},x_{k+1})\mapsto
x_{1}-y_{1}+\cdots+x_{k}-y_{k}+x_{k+1}\pmod{m},$

where $m=2$ for $\mathbf{A}_{1}$ and $m=3^{\prime}$ for $\mathbf{A}_{2}$. We
will now show that $\operatorname{BLP+AIP}$ fails to solve
$\operatorname{PCSP}(\mathbf{B},\mathbf{B})=\operatorname{CSP}(\mathbf{B})$;
to see why, suppose that it does solve it. Thus, by Theorem 9,
$\operatorname{Pol}(\mathbf{B},\mathbf{B})$ should contain a 2-block symmetric
polymorphism of arity 5, say
$f\in\operatorname{Pol}^{(5)}(\mathbf{B},\mathbf{B})$. For the ease of
notation, suppose that the first block of symmetry of $f$ contains the first 3
inputs, and the second block of symmetry contains the last 2 inputs (rather
than the blocks being based on parity). Now consider the following matrix

$\left(\begin{array}[]{ccc|cc}1^{\prime}&0^{\prime}&0^{\prime}&1&0\\\
0^{\prime}&1^{\prime}&0^{\prime}&0&1\\\
0^{\prime}&0^{\prime}&1^{\prime}&1&0\\\
1^{\prime}&0^{\prime}&0^{\prime}&0&1\\\
0^{\prime}&1^{\prime}&0^{\prime}&1&0\\\
0^{\prime}&0^{\prime}&1^{\prime}&0&1\\\ \end{array}\right)$

Every column of this matrix is an element of $R^{\mathbf{B}}$; thus $f$
applied to every row gives a tuple of $R^{\mathbf{B}}$. But, due to block-
symmetry, the image of every row through $f$ is the same! This contradicts the
lack of constant tuples in $\mathbf{B}$.

The non-solvability of $\operatorname{PCSP}(\mathbf{B},\mathbf{B})$ by
$\operatorname{AIP}$ is relevant in view of Conjecture 5 — it shows that the
“$\operatorname{AIP}$ being a universal algorithm for
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},-)$”
part of Conjecture 5 cannot be extended to _arbitrary_ symmetric templates. We
believe that it might hold true for any _connected_ $\mathbf{A}$ with one
symmetric relation.

See 4

###### Proof.

Such structures are super-connected by Lemma 35, which implies additivity and
dependency of $(\mathbf{A},\mathbf{B})$ by Lemma 31 and Lemma 32,
respectively. ∎

We will now move on to a proof of Theorem 1. Suppose $(\mathbf{A},\mathbf{B})$
is dependent and additive. Suppose generally that $A=[a]$.

######  Definition 40.

Consider a polymorphism $f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$.
We call it _$k$ -degenerate_ if there exist
$x_{1},\ldots,x_{k}\in\operatorname{range}(f^{p})$ such that for any
$S_{1},\ldots,S_{k}\subseteq[n]$ for which $f^{p}(S_{i})=x_{i}$ we have that
not all $S_{i}$ are disjoint. Note that no polymorphism can be 1-degenerate as
a single set is a disjoint family.

For any polymorphism $f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$, we
call a set $S\subseteq[n]$ a _hard set_ if, for any $T\supseteq S$, we have
$f^{p}(T)\neq f^{p}(\emptyset)$.999These two notions are similar to those of
_unbounded antichains_ and _fixing sets_ in [20]. The notion of hard-set is
similar to the notion of an $f(\emptyset)$-avoiding set from [18, 30].

We will prove Theorem 1 using the following two cases. For the following,
define $N_{d}=\max(1+|B|^{a^{2}}a^{2r_{\max}},3)$ and $N_{h}=|B|^{a^{2}}$,
where $r_{\max}$ is the maximum arity of any relation in $\mathbf{A}$.

######  Theorem 41.

If $\operatorname{Pol}(\mathbf{A},\mathbf{B})$ contains a polymorphism that is
not $k$-degenerate, for any $k\leq N_{d}$, and that has no hard sets of size
at most $N_{h}$, then $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is solved
by $\operatorname{AIP}$ and is finitely tractable.

######  Theorem 42.

If every polymorphism within $\operatorname{Pol}(\mathbf{A},\mathbf{B})$ is
$k$-degenerate for some $k\leq N_{d}$, or has a hard set of size at most
$N_{h}$, then $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is NP-hard.

These two theorems will be proved in their own sections later.

###### Proof of Theorem 1.

A result of Theorem 41 and Theorem 42. ∎

######  Remark 43.

The following turns out to be an equivalent characterisation of the
solvability of $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ for symmetric
$\mathbf{A}$ and functional $\mathbf{B}$. Suppose $\mathbf{A}$ has domain $A$
and relations $R_{1}^{\mathbf{A}},\ldots,R_{k}^{\mathbf{A}}$. For any positive
integer $m$, define a structure $\mathbf{A}_{m}$ in the following way. The
domain of $\mathbf{A}_{m}$ is the free $\mathbb{Z}_{m}$-module of functions
$\mathbb{Z}_{m}^{A}$. We will write elements of this module as formal sums of
the form $\sum_{a\in A}x_{i}\overline{a}$, where $x_{i}\in\mathbb{Z}_{m}$ and
$\\{\overline{a}\mid a\in A\\}$ is a basis for $\mathbb{Z}_{m}^{A}$. Extend
the map $x\mapsto\overline{x}$ to tuples of functions, in the following way:
$\overline{(x_{1},\ldots,x_{n})}=(\overline{x_{1}},\ldots,\overline{x_{n}})$.
To define the relation $R_{k}^{\mathbf{A}_{m}}$, consider the set of tuples of
functions $S=\\{\overline{t}\mid t\in R_{k}^{\mathbf{A}}\\}$. Tuples of
functions also form a free $\mathbb{Z}_{m}$-module; thus take
$R_{k}^{\mathbf{A}_{m}}$ to be the minimal affine space containing $S$.
Equivalently, $R_{k}^{\mathbf{A}_{m}}$ is the set of tuples that are
equivalent to some $t\in R_{k}^{\mathbf{A}}$ modulo $\\{t-t^{\prime}\mid
t,t^{\prime}\in R_{k}^{\mathbf{A}}\\}$, if the set of tuple of functions from
$\mathbb{Z}_{m}^{A}$ is seen as merely an Abelian group.

With the relational structure $\mathbf{A}_{m}$ thus defined, and noting that
$\mathbf{A}\to\mathbf{A}_{m}$ always via the homomorphism
$x\mapsto\overline{x}$, we note that our result is equivalent to the
following: for symmetric $\mathbf{A}$ and functional $\mathbf{B}$ where
$(\mathbf{A},\mathbf{B})$ is additive and dependent,
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is solvable in polynomial time if
and only if $\mathbf{A}\to\mathbf{A}_{m}\to\mathbf{B}$ for some positive
integer $m$. That this condition is sufficient is clear, as
$\operatorname{CSP}(\mathbf{A}_{m})$ is solved by $\operatorname{AIP}$ as per
Lemma 10. Necessity follow from our proof of Theorem 41 and Theorem 42.

We note also that $\mathbf{A}_{m}$ can also be described as a free structure
[6]. Namely, define $\mathcal{Z}_{m}$ to be a minion such that

$\mathcal{Z}_{m}^{(n)}=\\{(x_{n},\ldots,x_{n})\mid 0\leq
x_{1},\ldots,x_{n}<m,\sum_{i=1}^{n}x_{i}\equiv 1\pmod{m}\\},$

and let minoring be defined as follows. For
$x=(x_{1},\ldots,x_{n})\in\mathcal{Z}_{m}^{(n)}$, and for
$\pi:[n]\to[n^{\prime}]$, define $y=x^{\pi}$ by
$y_{i}=\sum_{\pi(j)=i}x_{j}\bmod m$. With this in mind, it can be seen that
$\mathbf{A}_{m}=\mathbf{F}_{\mathcal{Z}_{m}}(\mathbf{A})$.

###  4.1 Proof of Theorem 41

In this section we assume that
$\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$ has a polymorphism $f$ of
arity $n$ that is not $k$-degenerate for $k$ at most $N_{d}$, and has no hard
sets of size at most $N_{h}$. Given this, we will prove that
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is solved by $\operatorname{AIP}$
and is finitely tractable.

######  Definition 44.

Define $0=f^{p}(\emptyset)$ and $1=f^{p}([n])$.

######  Lemma 45.

$(\operatorname{range}(f^{p}),+,0)$ forms a group.101010This group happens to
be Abelian, but this is not needed for the proof.

###### Proof.

We prove this in a few parts.

Closure, well-definedness.

Consider $x,y\in\operatorname{range}(f^{p})$. As $f$ is not 2-degenerate,
there exist disjoint $S,T$ such that $f^{p}(S)=x,f^{p}(T)=y$. Thus
$x+y=f^{p}(S)+f^{p}(T)=f^{p}(S\cup T)\in\operatorname{range}(f^{p})$, so $+$
is closed and well-defined.

Associativity.

Consider any $x,y,z\in\operatorname{range}(f^{p})$. Since $f$ is not
3-degenerate, there exist disjoint $S,T,U\subseteq[n]$ such that
$f^{p}(S)=x,f^{p}(T)=y,f^{p}(U)=z$. Thus,

$x+(y+z)=x+f(T\cup U)=f(S\cup(T\cup U))=f((S\cup T)\cup U)=f(S\cup
T)+z=(x+y)+z.$

Identity element.

Consider any $x\in\operatorname{range}(f^{p})$. Suppose $f^{p}(S)=x$ for some
$S\subseteq[n]$. Thus, $x+0=f^{p}(S\cup\emptyset)=f^{p}(S)=x$.

Inverses.

Consider any $x\in\operatorname{range}(f^{p})$. Suppose that $f(S)=x$; by
Lemma 17, some $T\subseteq S$ exists with size at most $|B|^{a^{2}}$ such that
$f^{p}(T)=f^{p}(S)=x$. Since $f$ has no hard sets of size at most
$N_{h}=|B|^{a^{2}}$, $T$ is not a hard set, and thus some $U\supseteq T$
exists such that $f^{p}(U)=0$. Thus $x+f^{p}(U\setminus
T)=f^{p}(T)+f^{p}(U\setminus T)=f^{p}(U)=0$, so $x$ has an inverse.

Thus we conclude that $(\operatorname{range}(f^{p}),+,0)$ is a group. ∎

######  Definition 46.

Let $G$ be the Abelian subgroup of $(\operatorname{range}(f^{p}),+,0)$
generated by $1=f^{p}([n])$. Let $m$ be the order of $1$. Thus
$G\cong\mathbb{Z}_{m}$. Note that
$m\leq|\operatorname{range}(f^{p})|\leq|B|^{a^{2}}$. We will identify
$\mathbb{Z}_{m}$ with $G$ (e.g. we allow ourselves to write $1+1=2$, provided
$m\geq 3$, where $1,2\in\operatorname{range}(f^{p})$).

Define the Abelian group $(H,+)=G^{a}$. We will identify $H$ with
$\mathbb{Z}_{m}^{a}$. We will also define $0$ to be the 0 element in $H$ as
well as $G$.

For any $i\in[a]$, define $\overline{i}\in H$ as the unit vector that has a 1
at position $i$. For some tuple $(x_{1},\ldots,x_{s})\in{[a]}^{r}$, define
$\overline{(x_{1},\ldots,x_{s})}=(\overline{x_{1}},\ldots,\overline{x_{s}})\in
H^{r}$. Define $0$ to be the zero vector in $H^{r}$ as well.111111We can see
the elements of $H$ as frequency vectors modulo $m$. Indeed, for
$x_{1},\ldots,x_{n}\in[a]$, $\overline{x_{1}}+\cdots+\overline{x_{n}}$ counts
the number of appearances of $1,2,\ldots,a$ modulo $m$ among
$x_{1},\ldots,x_{n}$. In line with this, the elements of $H^{r}$ can be seen
as tuples of $r$ frequency vectors. Under this view, for
$t_{1},\ldots,t_{n}\in{[a]}^{r}$, the sum
$\overline{t_{1}}+\cdots+\overline{t_{n}}$ is a tuple of $r$ frequency
vectors, where the $i$-th frequency vector counts the frequencies of the
elements of $[a]$ among the $i$-th elements of the tuples
$t_{1},\ldots,t_{n}$, modulo $m$.

For any relation $R^{\mathbf{A}}$ of $\mathbf{A}$ of arity $r$, define
$M(R^{\mathbf{A}})$ to be the subgroup of $H^{r}$ generated by
$\overline{p}-\overline{q}$ for $p,q\in R^{\mathbf{A}}$. Since $H^{r}$ is
Abelian, $M(R^{\mathbf{A}})$ is a normal subgroup.

######  Lemma 47.

Fix some relation $R^{\mathbf{A}}$ of $\mathbf{A}$; suppose it has arity $r$.
Let $t$ be some tuple of $R^{\mathbf{A}}$. Define $M=M(R^{\mathbf{A}})$.
Consider any $(a_{1},\ldots,a_{s})\in H^{r}$ such that
$(a_{1},\ldots,a_{s})\equiv\overline{t}\bmod M$. There exists a matrix
$(x_{ij})$ with $N\leq N_{d}$ columns and $r$ rows, where $N\equiv 1\bmod m$,
with elements in $[a]$, such that each column is a tuple of $R^{\mathbf{A}}$,
and, for each row $i$, we have

$\sum_{j=1}^{N}\overline{x_{ij}}=a_{i}.$

###### Proof.

Note that every element in $H^{r}$ has order that divides $m$ (since
$H^{r}\cong{(G^{a})}^{r}\cong{(\mathbb{Z}_{m}^{a})}^{r}$). Thus, since
$(a_{1},\ldots,a_{s})\equiv\overline{t}\bmod M$, and since $M$ is generated by
$\overline{p}-\overline{q}$ for $p,q\in R^{\mathbf{A}}$, it follows that there
exist coefficients $c_{pq}\in\\{0,\ldots,m-1\\}$ for $p,q\in R^{\mathbf{A}}$
such that

$(a_{1},\ldots,a_{s})=\overline{t}+\sum_{p,q\in
R^{\mathbf{A}}}c_{pq}(\overline{p}-\overline{q})=\overline{t}+\sum_{p,q\in
R^{\mathbf{A}}}c_{pq}\overline{p}+(m-c_{pq})\overline{q}.$ (1)

This indicates the matrix we will use: let $(x_{ij})$ be a matrix whose first
column is $t$, and, for each $p,q\in R^{\mathbf{A}}$, has $c_{pq}$ columns
equal to $p$ and $m-c_{pq}$ columns equal to $q$. Clearly we use $N\leq
1+m|R^{\mathbf{A}}|^{2}=1+|B|^{a^{2}}a^{2r_{\max}}\leq N_{d}$ columns, and
$N\equiv 1\bmod m$. To see why $\sum_{j=1}^{N}\overline{x_{ij}}=a_{i}$ for
each $i$, note that this condition is equivalent to
$(a_{1},\ldots,a_{s})=\sum_{j=1}^{N}\overline{c_{j}}$, where
$c_{1},\ldots,c_{N}$ are the columns of the matrix. But this is precisely
Equation (1). Thus we have created the required matrix. ∎

######  Lemma 48.

Suppose $f=h\circ f^{\star}$. For every $N\leq N_{d}$ such that $N\equiv
1\bmod m$, the function $h_{N}:A^{N}\to B$ defined by

$h_{N}(x_{1},\ldots,x_{N})=h\left(\sum_{i=1}^{N}\overline{x_{i}}\right)$

is a polymorphism of $(\mathbf{A},\mathbf{B})$.

###### Proof.

By assumption, $f$ is not $N$-degenerate. Thus there exist disjoint subsets
$S_{1},\ldots,S_{N}$ of $[n]$ where
$f^{p}(S_{1})=\cdots=f^{p}(S_{N})=f^{p}([n])=1$. Let
$T=[n]\setminus(S_{1}\cup\ldots\cup S_{N})$. Note that $S_{1},\ldots,S_{N},T$
form a partition of $[n]$. Furthermore,

$1=f^{p}([n])=f^{p}(S_{1})+\cdots+f^{p}(S_{N})+f^{p}(T)=N+f^{p}(T)=1+f^{p}(T).$

The last equation holds as $N\equiv 1\bmod m$, and addition is done in
$G\cong\mathbb{Z}_{m}$. Thus $f^{p}(T)=0$.

Let $\pi:[n]\to[N+1]$ be a function that takes $x\in S_{i}$ to $i$ and $x\in
T$ to $N+1$. Consider the polymorphism $f^{\pi}$. Since $f=h\circ f^{\star}$,
by the definition of $f^{\star}$ we can see that

$f^{\pi}(U_{1},\ldots
U_{a})=h(f^{p}(\pi^{-1}(U_{1})),\ldots,f^{p}(\pi^{-1}(U_{a}))).$

Now consider $f^{p}(\pi^{-1}(U))$. Note that
$\pi^{-1}(U)=T_{U}\cup\bigcup_{i\in U\cap[N]}S_{i}$, where $T_{U}=U$ if
$N+1\in U$, and $T_{U}=\emptyset$ otherwise. Thus

$f^{p}(\pi^{-1}(U))=f^{p}\left(T_{U}\cup\bigcup_{i\in
U\cap[N]}S_{i}\right)=f^{p}(T_{U})+\sum_{i\in
U\cap[N]}f^{p}(S_{i})=0+\sum_{i\in U\cap[N]}1=|U\cap[N]|\bmod m,$

where $|U\cap[N]|\bmod m$ is taken as an element of $\mathbb{Z}_{m}\cong G$.
In other words,

$f^{\pi}(U_{1},\ldots,U_{a})=h(|U_{1}\cap[N]|\bmod
m,\ldots,|U_{a}\cap[N]|\bmod m).$

Suppose now that $U_{1},\ldots,U_{a}$ are the set family representation of the
input vector $x_{1},\ldots,x_{N+1}$ (i.e. $x_{i}=j$ if and only if $i\in
U_{j}$) and consider the sum $\sum_{i=1}^{N}\overline{x_{i}}$. The $j$-th
coordinate of this sum is the number of $j$’s that appear in
$x_{1},\ldots,x_{N}$, modulo $m$, i.e. $|U_{j}\cap[N]|\bmod m$. Thus we see
that the equation above is equivalent to

$f^{\pi}(x_{1},\ldots,x_{N+1})=h\left(\sum_{i=1}^{N}\overline{x_{i}}\right).$

This polymorphism ignores $x_{N+1}$, so we find that the function

$(x_{1},\ldots,x_{N})\mapsto h\left(\sum_{i=1}^{N}\overline{x_{i}}\right)$

is also a polymorphism. But this is just $h_{N}$, which is thus a polymorphism
as required. ∎

We can now prove the main theorem in this subsection.

###### Proof of Theorem 41.

We will show that $(\mathbf{A},\mathbf{B})$ admits a homomorphic sandwich
$\mathbf{A}\to\mathbf{E}\to\mathbf{B}$, where $\mathbf{E}$ is a relational
structure whose domain is $H$, and where each relation will be of the form (i)
$c+M$ for some $c\in H^{r}$ and $M\lhd H^{r}$, or (ii) empty. By Lemma 10 this
implies our desired conclusion. The homomorphism $\mathbf{A}\to\mathbf{E}$
will be given by the map $g(x)=\overline{x}$. The homomorphism
$\mathbf{E}\to\mathbf{B}$ will be given by any function $h$ for which
$f=h\circ f^{\star}$. (Recall that such a function exists by Lemma 20.) We
will construct $\mathbf{E}$ relation by relation, showing along the way that
$g$ and $h$ are in fact homomorphisms.

Consider some relation $R^{\mathbf{A}}$ of $\mathbf{A}$, of arity $r$, that
corresponds to a relation $R^{\mathbf{B}}$ of $\mathbf{B}$, and
$R^{\mathbf{E}}$ in $\mathbf{E}$. If $R^{\mathbf{A}}$ is empty then we can
simply set $R^{\mathbf{E}}$ to be empty, and then $g$ and $h$ map tuples of
$R^{\mathbf{A}}$ to tuples of $R^{\mathbf{E}}$, and then to tuples of
$R^{\mathbf{B}}$ vacuously. Thus, suppose $t=(t_{1},\ldots,t_{s})$ is some
tuple of $R^{\mathbf{A}}$, and let $M=M(R^{\mathbf{A}})$. Then we set
$R^{\mathbf{E}}=\overline{t}+M$; in other words, a tuple $x\in H^{r}$ will
belong to this relation if and only if $x\equiv\overline{t}\bmod M$.

We first show that $g$ maps $R^{\mathbf{A}}$ to
$R^{\mathbf{E}}=\overline{t}+M$. Indeed, consider any tuple $x\in
R^{\mathbf{A}}$. We know that $g(x)=\overline{x}$ by definition. Thus,
$g(x)=\overline{x}=\overline{t}+(\overline{x}-\overline{t})\in\overline{t}+M$.
Thus $g$ maps $R^{\mathbf{A}}$ to $\overline{t}+M$.

We now show that $h$ maps $R^{\mathbf{E}}=\overline{t}+M$ to $R^{\mathbf{B}}$.
Consider any tuple $(a_{1},\ldots,a_{s})\in\overline{t}+M$. By Lemma 47 there
exists some matrix $X=(x_{ij})$ with $N\leq N_{d}$ columns and $r$ rows, where
$N\equiv 1\bmod m$, such that each column is an element of $R^{\mathbf{A}}$,
and for each $i\in[r]$ we have

$\sum_{j=1}^{N}\overline{x_{ij}}=a_{i}.$

Furthermore, by Lemma 48, the function $h_{N}:A^{N}\to B$ given by

$h_{N}(x_{1},\ldots,x_{N})=h\left(\sum_{i=1}^{N}\overline{x_{i}}\right)$

is a polymorphism. Note now that

$(h(a_{1}),\ldots,h(a_{s}))=\left(h\left(\sum_{j=1}^{N}\overline{x_{1j}}\right),\ldots
h\left(\sum_{j=1}^{N}\overline{x_{sj}}\right)\right)\\\
=(h_{N}(x_{11},\ldots,x_{1N}),\ldots,h_{N}(x_{s1},\ldots,x_{sN}))\in
R^{\mathbf{B}}.$

The last inclusion holds since the tuple in question is the result of applying
$h_{N}$, a polymorphism of $(\mathbf{A},\mathbf{B})$, to the rows of a matrix
whose columns are elements in $R^{\mathbf{A}}$.

Thus we note that $\mathbf{A}\to\mathbf{E}\to\mathbf{B}$ for some structure
$\mathbf{E}$ that satisfies the conditions in Lemma 10. In conclusion,
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is solved by $\operatorname{AIP}$
and is finitely tractable. ∎

###  4.2 Proof of Theorem 42

In this section we will prove that
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is NP-hard if each polymorphism
$f\in\operatorname{Pol}(\mathbf{A},\mathbf{B})$ is $k$-degenerate for some $k$
at most $N_{d}$, or has a hard set of size at most $N_{h}$.

######  Lemma 49.

If $f\in\operatorname{Pol}(\mathbf{A},\mathbf{B})$ then $f$ cannot have more
than $|B|^{a^{2}}$ disjoint hard sets.

###### Proof.

Equivalently we show that any family $\mathcal{G}$ of more than $|B|^{a^{2}}$
disjoint sets contains a non-hard set. Apply Lemma 16 to $\mathcal{G}$ to find
a nonempty subfamily $\\{G_{1},\ldots\\}$ such that
$f^{p}(\bigcup_{i}G_{i})=f^{p}(\emptyset)$. Thus $G_{i}\in\mathcal{G}$ is not
a hard set. ∎

######  Lemma 50.

Suppose $f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$ and
$\pi:[n]\to[m]$. Then ${(f^{\pi})}^{p}=f^{p}\circ\pi^{-1}$.

###### Proof.

Note that $f_{ij}(S)=f(T_{1},\ldots,T_{a})$ where $T_{j}=S$,
$T_{i}=[n]\setminus S$, and all the other inputs are $\emptyset$. Now,
${(f^{\pi})}_{ij}(S)=f^{\pi}(T_{1},\ldots,T_{a})=f(\pi^{-1}(T_{1}),\ldots,\pi^{-1}(T_{a}))=f^{p}(\pi^{-1}(S))$,
and so ${(f^{\pi})}_{ij}=f_{ij}\circ\pi^{-1}$. Our conclusion follows by
applying this fact for each $i,j\in A$. ∎

######  Lemma 51.

Suppose $f\in\operatorname{Pol}^{(n)}(\mathbf{A},\mathbf{B})$ and
$\pi:[n]\to[m]$. If $S$ is a hard set of $f$ then $\pi(S)$ is a hard set of
$f^{\pi}$.

###### Proof.

We prove this by contrapositive. Suppose $\pi(S)$ is not a hard set of
$f^{\pi}$. Then some $T\supseteq\pi(S)$ exists such that
${(f^{\pi})}^{p}(T)={(f^{\pi})}^{p}(\emptyset)$. So
$(f^{p})(\pi^{-1}(T))={(f^{\pi})}^{p}(T)={(f^{\pi})}^{p}(\emptyset)=(f^{p})(\pi^{-1}(\emptyset))=f^{p}(\emptyset)$.
Thus $f^{p}(\pi^{-1}(T))=f^{p}(\emptyset)$, and $S$ is not a hard set, as
$S\subseteq\pi^{-1}(T)$. ∎

Let $\mathcal{M}_{h}$ denote the subset of
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ whose polymorphisms have hard sets
of size at most $N_{h}$. Let $\mathcal{M}_{x_{1},\ldots,x_{k}}$ denote the
subset of $\operatorname{Pol}(\mathbf{A},\mathbf{B})$ whose polymorphisms are
$k$-degenerate, yet not $(k-1)$-degenerate, where $x_{1},\ldots,x_{k}\in
B^{A^{2}}$ are witnesses to this degeneracy. By assumption, and as no
polymorphism is $1$-degenerate,

$\operatorname{Pol}(\mathbf{A},\mathbf{B})=\mathcal{M}_{h}\cup\bigcup_{k=2}^{N_{d}}\bigcup_{x_{1}\in\operatorname{range}(f^{p})}\ldots\bigcup_{x_{k}\in\operatorname{range}(f^{p})}\mathcal{M}_{x_{1},\ldots,x_{k}}.$
(2)

######  Lemma 52.

There exists some assignment $I$ that takes $f\in\mathcal{M}_{h}^{(n)}$ to a
subset of $[n]$ of size at most $|B|^{2a^{2}}$ such that, whenever
$g\in\mathcal{M}_{h}^{(m)}$ and $g=f^{\pi}$ for some $\pi:[n]\to[m]$, we have
that $\pi(I(f))\cap I(g)\neq\emptyset$.

###### Proof.

To construct $I(f)$, let $S_{1},\ldots$ be a maximal sequence of disjoint hard
sets of $f$ of size at most $|B|^{a^{2}}$, constructed greedily, and then set
$I(f)$ to be the union of these sets. Since there can be at most $|B|^{a^{2}}$
disjoint hard sets by Lemma 49, it follows that $|I(f)|\leq|B|^{2a^{2}}$.

Consider now any $f,g\in\mathcal{M}_{h}$ such that $g=f^{\pi}$. Note that
$I(f)$ contains within it a hard set $S$ of size at most $|B|^{a^{2}}$. Thus
$\pi(I(f))\supseteq\pi(S)$, which is a hard set of size at most $|B|^{a^{2}}$
by Lemma 51, and thus must intersect $I(g)$ by maximality. It follows that
$\pi(I(f))\cap I(g)\neq\emptyset$. ∎

######  Lemma 53.

For $k\geq 2,x_{1},\ldots,x_{k}\in\operatorname{range}(f^{p})$, there exists
some assignment $I$ that takes $f\in\mathcal{M}^{(n)}_{x_{1},\ldots,x_{k}}$ to
a subset of $[n]$ of size at most $k|B|^{a^{2}}$ such that, whenever
$g\in\mathcal{M}^{(m)}_{x_{1},\ldots,x_{k}}$ and $g=f^{\pi}$ for some
$\pi:[n]\to[m]$ we have that $\pi(I(f))\cap I(g)\neq\emptyset$.

###### Proof.

To construct $I(f)$, take $S_{1},\ldots,S_{k-1}$ to be disjoint sets such that
$f^{p}(S_{i})=x_{i}$, and take $T$ to be any set such that $f(T)=x_{k}$. Such
sets exist since $f$ is not $(k-1)$-degenerate, and we can take all of these
sets to be of size at most $|B|^{a^{2}}$, by replacing them with the subsets
given by Lemma 17. Let $I(f)$ be the union of $S_{1},\ldots,S_{k-1},T$. Note
that $|I(f)|\leq k|B|^{a^{2}}$.

Consider now any $f,g\in\mathcal{M}_{x_{1},\ldots,x_{k}}$ such that
$g=f^{\pi}$. Note that $I(f)$ contains within it disjoint sets
$S_{1},\ldots,S_{k-1}$ such that $f^{p}(S_{i})=x_{i}$, and $I(g)$ contains
within it a set $T$ such that $g^{p}(T)=x_{k}$. Now,
$f^{p}(\pi^{-1}(T))={(f^{\pi})}^{p}(T)=g^{p}(T)=x_{k}$, and thus by the
$k$-degeneracy of $f$ and the disjointness of $S_{1},\ldots,S_{k-1}$ it
follows that $\pi^{-1}(T)$ and $S_{1},\ldots,S_{k-1}$ must intersect. It
follows that $\pi(I(f))\cap I(g)\neq\emptyset$, as required. ∎

###### Proof of Theorem 42.

We see in (2) that $\operatorname{Pol}(\mathbf{A},\mathbf{B})$ is the union of
$m=1+\sum_{k=2}^{N_{d}}{({|B|}^{a^{2}})}^{k}$ sets, each of which has an
assignment $I$ that satisfies the condition of Theorem 11 if we take
$C=\max(N_{d}|B|^{a^{2}},|B|^{2a^{2}})$. Thus
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is NP-hard. ∎

##  5 $\bm{\textbf{BLP+AIP}=\textbf{AIP}}$ when $\mathbf{A}$ has one balanced
relation

In this section we prove Theorem 6 and Corollary 7. Recall that we call a
relation $R$ balanced if there exists a matrix $M$ whose columns are tuples of
$R$, where each tuple of $R$ appears as a column (possibly a multiple times),
and where the rows of $M$ are permutations of each other.

See 6

Suppose that $A=[a]$, and the relation of $\mathbf{A}$ is $R=R^{\mathbf{A}}$.
Furthermore suppose that each element in $[a]$ appears in $R$ (otherwise these
elements can just be eliminated from $A$). Suppose
$A\neq\emptyset,R\neq\emptyset$ (otherwise the conclusion is trivially true).
We name the columns of the matrix that witness the balancedness of $R$ as
$t_{1},\ldots,t_{N}\in R$.

For any $i\in[a]$, let $\overline{i}$ be a unit vector in $\mathbb{Z}^{a}$;
i.e., it has a 1 at position $i$. For any tuple $(a_{1},\ldots,a_{r})\in
A^{r}$, let
$\overline{(a_{1},\ldots,a_{r})}=(\overline{a_{1}},\ldots,\overline{a_{r}})\in{(\mathbb{Z}^{a})}^{r}$.
Let $\overline{R}=\\{\overline{t}\mid t\in
R\\}\subseteq{(\mathbb{Z}^{a})}^{r}$. (We see the elements of $\mathbb{Z}^{a}$
as frequency vectors, and the elements of ${(\mathbb{Z}^{a})}^{r}$ as tuples
of frequency vectors.) Endow all of these with additive structure. For any
$k\in\mathbb{Z}$, we denote by $k\overline{R}$ the set of sums of $k$ vectors
from $\overline{R}$.

######  Lemma 54.

$(k+1)\overline{R}-k\overline{R}+k\sum_{i}\overline{t_{i}}\subseteq(kN+1)\overline{R}$.

###### Proof.

If $x\in(k+1)\overline{R}-k\overline{R}+k\sum_{i}\overline{t_{i}}$, it can be
written as a sum of $k+1$ vectors from $\overline{R}$, minus $k$ vectors from
$\overline{R}$, plus $k$ copies of each vector $\overline{t_{i}}$. Since each
tuple of $R$ appears among $t_{1},\ldots,t_{N}$, the last $kN$ vectors in the
sum above include at least $k$ copies of each vector in $\overline{R}$. By
removing the $k$ subtracted vectors from the $k$ copies of each vector from
$\overline{R}$, we find that $x$ can be written as a sum of $k+1-k+kN=kN+1$
vectors from $\overline{R}$, i.e. $x\in(kN+1)\overline{R}$. ∎

For any $k\in\mathbb{Z}$, we define $S_{k}\subseteq\mathbb{Z}^{a}$ to be the
set of sequences of integers that sum up to $k$, with non-negative
coordinates.

######  Lemma 55.

If $(\mathbf{A},\mathbf{B})$ has a 2-block-symmetric polymorphism $f$ of arity
$2k+1$ then there exists a function $g:S_{k}\times S_{k+1}\rightarrow B$ such
that $(g(x_{1},y_{1}),\ldots,g(x_{r},y_{r}))\in R^{\mathbf{B}}$ for all
$(x_{1},\ldots,x_{r})\in
k\overline{R},(y_{1},\ldots,y_{r})\in(k+1)\overline{R}$.

###### Proof.

To compute $g(x,y)$, create two sequences of elements in $[a]$, of lengths $k$
and $k+1$, whose frequencies correspond to $x$ and $y$ respectively (i.e. the
sequence for $x=(x_{1},\ldots,x_{a})$ has $x_{i}$ appearances of $i$), and
interleave these to create a sequence $a_{1},\ldots a_{2k+1}$. Then
$g(x,y)=f(a_{1},\ldots,a_{2k+1})$.

To see why this function satisfies the required condition, suppose
$(x_{1},\ldots,x_{r})\in k\overline{R}$ and
$(y_{1},\ldots,y_{r})\in(k+1)\overline{R}$. Thus we can, by definition, create
matrices $M$ and $N$, with $k$ and $k+1$ columns respectively, and $r$ rows,
where each column is an element of $R$, and each row $i$ has frequencies
corresponding to $x_{i}$ and $y_{i}$ respectively. Interleave the columns of
these matrices to create a matrix $A$. Apply $f$ to the rows of $A$. We find
that the image of row $i$ of $A$ is $g(x_{i},y_{i})$ by the symmetry of $f$;
furthermore, the images of the rows of $A$ must form a tuple of
$R^{\mathbf{B}}$, since $f$ is a polymorphism. This is the desired conclusion.
∎

######  Lemma 56.

Assume there exists a function $f:(S_{k+1}-S_{k})\to B$ such that
$(f(x_{1}),\ldots,f(x_{r}))\in\leavevmode\nobreak\ R^{\mathbf{B}}$ for any
$x_{1},\ldots,x_{r}\in S_{k+1}-S_{k}$ with
$(x_{1},\ldots,x_{r})\in(k+1)\overline{R}-k\overline{R}$. Then,
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ has an alternating polymorphism
of arity $2k+1$.

###### Proof.

If such a function exists, then

$g(x_{1},\ldots,x_{2k+1})=f(\overline{x_{1}}+\overline{x_{3}}+\cdots+\overline{x_{2k+1}}-\overline{x_{2}}-\overline{x_{4}}-\cdots-\overline{x_{2k}})$

is the required polymorphism. ∎

###### Proof of Theorem 6.

By Theorem 8, $\operatorname{AIP}$ solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if and only if
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ contains alternating operations of
all odd arities. By Theorem 9, $\operatorname{BLP+AIP}$ solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if and only if
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ contains 2-block-symmetric
operations of all odd arities. As any alternating operation is 2-block-
symmetric, it follows that any PCSP solved by $\operatorname{AIP}$ is also
solved by $\operatorname{BLP+AIP}$.121212This also directly follows from the
definitions of the $\operatorname{AIP}$ and $\operatorname{BLP+AIP}$
algorithms [10]. It suffices to show that 2-block-symmetric operations in
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ imply alternating operations.

Fix some natural number $k$; we will now show that there exists an alternating
operation in $\operatorname{Pol}(\mathbf{A},\mathbf{B})$ of arity $2k+1$.
Since $\operatorname{Pol}(\mathbf{A},\mathbf{B})$ contains a 2-block-symmetric
operation of arity $2kN+1$, let $f:S_{kN}\times S_{kN+1}\to B$ be the function
given by Lemma 55. We will construct the function required by Lemma 56 in
order to prove the existence of an alternating polymorphism.

Consider the vector $v=\sum_{i}\overline{t_{i}}\in{(\mathbb{Z}^{a})}^{r}$. We
claim that $v$ is a constant vector. To see why this is the case, observe that
one way to compute $\sum_{i}\overline{t_{i}}$ is to make $t_{1},\ldots,t_{N}$
into the columns of a matrix, and then to compute the frequencies of each
element of $[a]$ in each row. Element $i$ of $v$ is a tuple, where element $j$
is the number of appearances of $j$ in row $i$ in this matrix. But, since
$t_{1},\ldots,t_{N}$ witness the balancedness of $R$, these frequencies are
equal for each row. Thus $v$ is indeed a constant vector; suppose that
$v=(c,\ldots,c)$ for some $c\in S_{N}$. Note that each element in $[a]$
appears in some tuple of $R$ by assumption, and each tuple of $R$ appears in
the sum $\sum_{i}\overline{t_{i}}$. Thus each coordinate in
$c\in\mathbb{Z}^{a}$ is at least 1.

The function we are interested in is $g:(S_{k+1}-S_{k})\to B$, where
$g(x)=f\left(kc,x+kc\right)$. First note that these inputs are legal inputs
for the function $f$. To see why, note first that $c\in S_{N}$ and thus $kc\in
S_{kN}$. Second, consider $x+kc$. As $x\in S_{k+1}-S_{k}$, the elements in $x$
sum up to 1. Since the elements in $kc$ sum up to $kN$, it follows that the
elements in $x+kc$ sum up to $1+kN$ as required. Furthermore, all the elements
of $x+kc$ are non-negative: each element of $x$ is at least $-k$, whereas each
element of $c$ is at least 1, and thus each element of $kc$ is at least $k$.
Thus $x+kc\in S_{kN+1}$.

Why does $g$ satisfy the conditions from Lemma 56? Consider any
$x_{1},\ldots,x_{r}\in S_{k+1}-S_{k}$ such that
$(x_{1},\ldots,x_{r})\in(k+1)\overline{R}-k\overline{R}$. Note that

$\displaystyle(kc,\ldots,kc)=k(c,\ldots,c)=k\sum_{i}\overline{t_{i}}\in
kN\overline{R},$
$\displaystyle(x_{1}+kc,\ldots,x_{r}+kc)=(x_{1},\ldots,x_{r})+k(c,\ldots,c)\in(k+1)\overline{R}-k\overline{R}+k\sum_{i}\overline{t_{i}}\subseteq(kN+1)\overline{R},$

due to Lemma 54. Thus, since $f$ satisfies the conditions in Lemma 55,

$(g(x_{1}),\ldots,g(x_{r}))=\left(f\left(kc,x_{1}+kc\right),\ldots,f\left(kc,x_{r}+kc\right)\right)\in
R^{B}.$

Thus $(g(x_{1}),\ldots,g(x_{r}))\in R^{\mathbf{B}}$, as required. ∎

Theorem 6 does not generalise to structures with multiple relations (even just
two), as the following examples show.

######  Remark 57.

Consider a Boolean symmetric template $\mathbf{A}$ that has two balanced (and
in fact even symmetric) relations, namely $R^{\mathbf{A}}=\\{(0)\\}$ and
$Q^{\mathbf{A}}=\\{(0,1),(1,0),(1,1)\\}$, which are unary and binary,
respectively. Then $\operatorname{CSP}(\mathbf{A})$ is solved by
$\operatorname{BLP+AIP}$, and indeed by $\operatorname{BLP}$, since the
symmetric operation $\max(x_{1},\ldots,x_{n})$ is a polymorphism for any $n$
[6], but _not_ by $\operatorname{AIP}$. This is because $\mathbf{A}$ fails to
have any alternating non-unary polymorphisms, even of arity 3: suppose
$f(x,y,z)$ is such a polymorphism. Then $f(1,1,0)=f(0,0,0)=f(0,1,1)$ as $f$ is
alternating; and $f(0,0,0)=0$ due to $R^{\mathbf{A}}$. However, due to
$Q^{\mathbf{A}}$, $f(1,1,0)$ and $f(0,1,1)$ cannot both be 0. This
contradiction implies our conclusion.

One cannot simply remove the balancedness condition from Theorem 6, as the
following example shows.

######  Remark 58.

Let $\mathbf{A}$ be a Boolean template with relation
$S^{\mathbf{A}}=\\{(0,0,1),(0,1,0),(0,1,1)\\}$. Note that $S^{\mathbf{A}}$ is
_not_ balanced. Then $\operatorname{CSP}(\mathbf{A})$ is solved by
$\operatorname{BLP+AIP}$, and indeed by $\operatorname{BLP}$, since the
symmetric operation $\max(x_{1},\ldots,x_{n})$ is a polymorphism for any $n$
[6], but not by $\operatorname{AIP}$. $\mathbf{A}$ fails to have any
alternating polymorphism, even of arity 3, for exactly the same reason as the
problem from Remark 57. (The identities that would result from
$R^{\mathbf{A}}$ in that example now result from the first element in each
tuple in $S^{\mathbf{A}}$, and the identities that would result from
$Q^{\mathbf{A}}$ in that example now result from the last two elements in each
tuple in $S^{\mathbf{A}}$.)

On the other hand, there are templates that are unbalanced for which
$\operatorname{AIP}$ and $\operatorname{BLP+AIP}$ have equivalent power, as
the following example shows.

######  Remark 59.

Consider a Boolean template $\mathbf{A}$ that has one relation
$P^{\mathbf{A}}=\\{(0,1)\\}$. Then $\operatorname{CSP}(\mathbf{A})$ is solved
by $\operatorname{AIP}$ and by $\operatorname{BLP+AIP}$, since the alternating
operation $x_{1}+\cdots+x_{n}\bmod 2$ is a polymorphism of $\mathbf{A}$ for
every odd $n$. This is in spite of the fact that $P^{\mathbf{A}}$ is
unbalanced.

We now prove Corollary 7.

See 7

###### Proof.

Let $R$ be the relation of $\mathbf{A}$, of arity $r$. It is sufficient to
show that $R$ is balanced. Let $M$ be a matrix whose columns are the tuples of
$R$. Suppose that the rows of $M$ are $r_{1},\ldots,r_{n}$. We show that row
$i$ is a permutation of row $j$, for arbitrary $i,j\in[r]$.

Represent the elements of $G$ as permutation matrices. Let $\pi\in G$ be a
permutation (matrix) that sends $i$ to $j$ (it exists by transitivity).
Consider $\pi M$. Note that no two columns of $\pi M$ can be equal, since then
two columns of $\pi^{-1}\pi M=M$ would be equal, which is false. Furthermore
each column of $\pi M$ is a tuple of $R$, and thus a column of $M$, since $R$
is preserved by $\pi$. Thus we see that $\pi M$ can be seen as $M$ but with
its columns permuted. In other words, for some permutation matrix $\sigma$, we
have $\pi M=M\sigma^{T}$.

Now, let us look at row $j$ in $\pi M=M\sigma^{T}$. In $\pi M$ this is $r_{i}$
(since $\pi$ sends $i$ to $j$). In $M\sigma^{T}$ this is $r_{j}\sigma^{T}$.
Thus $r_{i}=r_{j}\sigma^{T}$, i.e. row $i$ of $M$ and row $j$ of $M$ are
permutations of each other. We conclude that $R$ is balanced, as required. ∎

Corollary 7 applies to fewer structures than Theorem 6, as shown in the next
example.

######  Remark 60.

Consider any digraph $\mathbf{A}$ with edge relation $E^{\mathbf{A}}$ that is
strongly connected but not symmetric. Then $E^{\mathbf{A}}$ is balanced (cf.
Appendix A). On the other hand, the unique transitive permutation group with
degree 2 (i.e. the group containing the identity permutation and the
permutation swapping two elements) does not preserve $E^{\mathbf{A}}$.

##  6 Conclusion

Our first result classifies certain
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, where $\mathbf{A}$ and
$\mathbf{B}$ are symmetric and $\mathbf{B}$ is functional, into being either
NP-hard or solvable in polynomial time. This is the first step towards the
following more general problem.

######  Problem 61.

Classify the complexity of $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ for
functional $\mathbf{B}$.

Looking more specifically at the case
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{B})$,
we note that our proof of Theorem 1 implies that, for functional $\mathbf{B}$,
we have that
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{B})$
is tractable if and only if $\mathbf{Eqn}_{m,1}\to\mathbf{B}$ for some
$m\leq|B|$, where $\mathbf{Eqn}_{m,1}$ is a relational structure over
$\\{0,\ldots,m-1\\}$ with one ternary relation defined by $x+y+z\equiv 1\bmod
m$. By using the Chinese remainder theorem,
$\mathbf{Eqn}_{m,1}=\mathbf{Eqn}_{3^{p},1}\times\mathbf{Eqn}_{q,1}$, where $q$
is coprime to 3. Since this latter template contains a constant tuple (namely
$(x,x,x)$ where $x$ is the inverse of 3 modulo $q$), we find that, for
functional $\mathbf{B}$,
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{B})$
is tractable if and only if $\mathbf{Eqn}_{3^{p},1}\to\mathbf{B}$.

Looking at non-functional templates
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{B})$
that are tractable, all the examples the authors are aware of are either
tractable for the same reason as a functional template is (i.e.
$\mathbf{Eqn}_{3^{p},1}\to\mathbf{B}$), or because they include the not-all-
equal predicate (i.e. $\mathbf{NAE}\to\mathbf{B}$). Thus, we pose the
following problem.

######  Problem 62.

Is
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{B})$
tractable if and only if
$\mathbf{Eqn}_{3^{p},1}\times\mathbf{NAE}\to\mathbf{B}$ for some $p$?

Problem 62 has a link with the problem of determining the complexity of
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{C}_{k}^{+})$,
where $\mathbf{C}_{k}^{+}$ is a ternary symmetric template on domain $[k]$
which contains tuples of the form $(1,1,2),\ldots,(k-1,k-1,k),(k,k,1)$, as
well as all tuples of three distinct elements (rainbow tuples). Such templates
are called _cyclic_ , with the cycle being $1\to\ldots\to k\to 1$.

The link is the following: $\mathbf{Eqn}_{3^{p},1}\times\mathbf{NAE}$ is a
template containing one cycle of length $2\times 3^{p}$, together with certain
rainbow tuples — in other words,
$\mathbf{Eqn}_{3^{p},1}\times\mathbf{NAE}\to\mathbf{C}_{2\times 3^{p}}^{+}$.
Likewise, $\mathbf{Eqn}_{3^{p},1}$ has a cycle of length $3^{p}$ and some
rainbow tuples, i.e. $\mathbf{Eqn}_{3^{p},1}\to\mathbf{C}_{3^{p}}^{+}$. That
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{C}_{k}^{+})$
is tractable whenever $k=3^{p}$ or $k=2\times 3^{p}$ was first observed in
[11]. If Problem 62 were answered in the affirmative then we would have that
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{C}_{k}^{+})$
is tractable if and only if $k=3^{p}$ or $k=2\times 3^{p}$. In particular,
this would mean that
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{C}_{4}^{+})$
is NP-hard, as conjectured in [5].131313Our structure $\mathbf{C}_{4}^{+}$ is
called $\textbf{\v{C}}^{+}$ in [5].

Answering Problem 62 in the affirmative would resolve Conjecture 5, i.e.,
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{B})$
would be tractable (via $\operatorname{AIP}$) if and only if
$\mathbf{Eqn}_{3^{p},1}\times\mathbf{NAE}\to\mathbf{B}$. Perhaps determining
whether this equivalence is true might be easier than resolving Conjecture 5;
thus we pose the following problem.

######  Problem 63.

Is
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{B})$
solved by $\operatorname{AIP}$ if and only if
$\mathbf{Eqn}_{3^{p},1}\times\mathbf{NAE}\to\mathbf{B}$ for some $p$?

There already exists such a characterisation for the power of
$\operatorname{AIP}$ using an infinite structure [6]. In particular, if we let
$\mathbf{Z}$ be an infinite structure whose domain is $\mathbb{Z}$, and with a
tuple $(x,y,z)$ in the relation if and only if $x+y+z=1$, then
$\operatorname{PCSP}(\mathbf{1}\textbf{-}\mathbf{in}\textbf{-}\mathbf{3},\mathbf{B})$
is solved by $\operatorname{AIP}$ if and only if $\mathbf{Z}\to\mathbf{B}$. We
are interested in a finite template of this kind.

Turning from problems to algorithms, our second result shows us that, for
certain problems of the form $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$
where $\mathbf{B}$ _need not be functional_ , and $\mathbf{A},\mathbf{B}$ have
one relation, $\operatorname{AIP}$ and $\operatorname{BLP+AIP}$ have the same
power. A natural question is for which other templates is it true?

######  Problem 64.

For which templates $(\mathbf{A},\mathbf{B})$ do $\operatorname{AIP}$ and
$\operatorname{BLP+AIP}$ have the same power?

Equivalently [6, 10], for which templates $(\mathbf{A},\mathbf{B})$ does the
existence of 2-block symmetric operations of all odd arities in
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ imply the existence of alternating
operations of all odd arities in $\operatorname{Pol}(\mathbf{A},\mathbf{B})$?

We remark that the recent work [16] does not answer any problem from this
section, and the results from [16] are consistent with positive answers to
Problems 62 and 63.

## References

  * [1] Martin Aigner and Günter M. Ziegler.  Proofs from THE BOOK.  Springer Publishing Company, Incorporated, Germany, 4th edition, 2009\.
  * [2] Kristina Asimi and Libor Barto.  Finitely tractable promise constraint satisfaction problems.  In Proc. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS’21), volume 202 of LIPIcs, pages 11:1–11:16, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.MFCS.2021.11.
  * [3] Albert Atserias and Víctor Dalmau.  Promise Constraint Satisfaction and Width.  In Proc. 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA’22), pages 1129–1153, USA, 2022. SIAM.  arXiv:2107.05886, doi:10.1137/1.9781611977073.48.
  * [4] Per Austrin, Venkatesan Guruswami, and Johan Håstad.  (2+$\epsilon$)-Sat is NP-hard.  SIAM J. Comput., 46(5):1554–1573, 2017.  URL: https://eccc.weizmann.ac.il/report/2013/159/, doi:10.1137/15M1006507.
  * [5] Libor Barto, Diego Battistelli, and Kevin M. Berg.  Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case.  In Proc. 38th International Symposium on Theoretical Aspects of Computer Science (STACS’21), volume 187 of LIPIcs, pages 10:1–10:16, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  arXiv:2010.04623, doi:10.4230/LIPIcs.STACS.2021.10.
  * [6] Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal.  Algebraic approach to promise constraint satisfaction.  J. ACM, 68(4):28:1–28:66, 2021.  arXiv:1811.00970, doi:10.1145/3457606.
  * [7] Libor Barto and Marcin Kozik.  Combinatorial Gap Theorem and Reductions between Promise CSPs.  In Proc. 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA’22), pages 1204–1220, USA, 2022. SIAM.  arXiv:2107.09423, doi:10.1137/1.9781611977073.50.
  * [8] Joshua Brakensiek and Venkatesan Guruswami.  Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.  SIAM J. Comput., 50(6):1663–1700, 2021.  arXiv:1704.01937, doi:10.1137/19M128212X.
  * [9] Joshua Brakensiek and Venkatesan Guruswami.  The quest for strong inapproximability results with perfect completeness.  ACM Trans. Algorithms, 17(3):27:1–27:35, 2021.  URL: https://eccc.weizmann.ac.il/report/2017/080/, doi:10.1145/3459668.
  * [10] Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný.  The power of the combined basic LP and affine relaxation for promise CSPs.  SIAM J. Comput., 49:1232–1248, 2020.  arXiv:1907.04383, doi:10.1137/20M1312745.
  * [11] Alex Brandts.  Promise Constraint Satisfaction Problems.  PhD thesis, University of Oxford, 2022.  URL: {https://ora.ouls.ox.ac.uk/objects/uuid:5efeff56-d5c8-42e8-9bd2-95243a1367ad}.
  * [12] Alex Brandts, Marcin Wrochna, and Stanislav Živný.  The complexity of promise SAT on non-Boolean domains.  ACM Trans. Comput. Theory, 13(4):26:1–26:20, 2021.  arXiv:1911.09065, doi:10.1145/3470867.
  * [13] Alex Brandts and Stanislav Živný.  Beyond PCSP(1-in-3,NAE).  Inf. Comput., 289(Part A):104954, 2022.  arXiv:2104.12800, doi:10.1016/j.ic.2022.104954.
  * [14] Andrei Bulatov, Peter Jeavons, and Andrei Krokhin.  Classifying the complexity of constraints using finite algebras.  SIAM J. Comput., 34(3):720–742, 2005.  doi:10.1137/S0097539700376676.
  * [15] Andrei A. Bulatov.  A dichotomy theorem for nonuniform CSPs.  In Proc. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS’17), pages 319–330, USA, 2017. IEEE.  arXiv:1703.03021, doi:10.1109/FOCS.2017.37.
  * [16] Lorenzo Ciardo, Marcin Kozik, Andrei Krokhin, Tamio-Vesa Nakajima, and Stanislav Živný.  On the complexity of the approximate hypergraph homomorphism problem, 2023\.  arXiv:2302.03456.
  * [17] Lorenzo Ciardo and Stanislav Živný.  CLAP: A New Algorithm for Promise CSPs.  SIAM J. Comput., 52(1):1–37, 2023.  arXiv:2107.05018, doi:10.1137/22m1476435.
  * [18] Irit Dinur, Oded Regev, and Clifford Smyth.  The hardness of 3-uniform hypergraph coloring.  Comb., 25(5):519–535, 2005.  doi:10.1007/s00493-005-0032-4.
  * [19] 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 J. Comput., 28(1):57–104, 1998.  doi:10.1137/S0097539794266766.
  * [20] Miron Ficak, Marcin Kozik, Miroslav Olšák, and Szymon Stankiewicz.  Dichotomy for Symmetric Boolean PCSPs.  In Proc. 46th International Colloquium on Automata, Languages, and Programming (ICALP’19), volume 132, pages 57:1–57:12, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  arXiv:1904.12424, doi:10.4230/LIPIcs.ICALP.2019.57.
  * [21] M. R. Garey and D. S. Johnson.  The complexity of near-optimal graph coloring.  J. ACM, 23(1):43–49, 1976.  doi:10.1145/321921.321926.
  * [22] Venkatesan Guruswami and Sai Sandeep.  d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors.  In Proc. 47th International Colloquium on Automata, Languages, and Programming (ICALP’20), volume 168 of LIPIcs, pages 62:1–62:12, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://eccc.weizmann.ac.il/report/2019/116/, doi:10.4230/LIPIcs.ICALP.2020.62.
  * [23] Pavol Hell and Jaroslav Nešetřil.  On the Complexity of ${H}$-coloring.  J. Comb. Theory, Ser. B, 48(1):92–110, 1990.  doi:10.1016/0095-8956(90)90132-J.
  * [24] Peter G. Jeavons.  On the Algebraic Structure of Combinatorial Problems.  Theor. Comput. Sci., 200(1-2):185–204, 1998.  doi:10.1016/S0304-3975(97)00230-2.
  * [25] Andrei Krokhin and Jakub Opršal.  An invitation to the promise constraint satisfaction problem.  ACM SIGLOG News, 9(3):30–59, 2022.  doi:10.1145/3559736.3559740.
  * [26] Andrei A. Krokhin, Jakub Opršal, Marcin Wrochna, and Stanislav Živný.  Topology and adjunction in promise constraint satisfaction.  SIAM J. Comput., 52(1):38–79, 2023.  arXiv:2003.11351, doi:10.1137/20m1378223.
  * [27] Tamio-Vesa Nakajima and Stanislav Živný.  Linearly Ordered Colourings of Hypergraphs.  ACM Trans. Comput. Theory, 14(3–4):12:1–12:19, 2022.  arXiv:2204.05628, doi:10.1145/3570909.
  * [28] Tamio-Vesa Nakajima and Stanislav Živný.  Boolean symmetric vs. functional PCSP dichotomy.  In Proc. 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’23). IEEE, 2023.
  * [29] Thomas Schaefer.  The complexity of satisfiability problems.  In Proc. 10th Annual ACM Symposium on the Theory of Computing (STOC’78), pages 216–226, USA, 1978. ACM.  doi:10.1145/800133.804350.
  * [30] Marcin Wrochna.  A note on hardness of promise hypergraph colouring, 2022.  arXiv:2205.14719.
  * [31] Dmitriy Zhuk.  A proof of the CSP dichotomy conjecture.  J. ACM, 67(5):30:1–30:78, 2020.  arXiv:1704.01914, doi:10.1145/3402029.

##  Appendix A Deferred proofs

######  Lemma 65.

A digraph $\mathbf{A}$ is balanced if and only if it is a disjoint union of
strongly connected components.

###### Proof.

If the relation of $\mathbf{A}$ is balanced, then there exists a collection of
tours of $\mathbf{A}$ containing every edge at least once. These exist since
the multi-digraph formed by the columns of the matrix witnessing the
balancedness of the relation of $\mathbf{A}$ is Eulerian. Thus, considering
the tour that contains some edge $(u,v)$, we see that there exists a walk from
$v$ to $u$. It follows that every weakly connected component of $\mathbf{A}$
is strongly connected, or equivalently $\mathbf{A}$ is the disjoint union of
strongly connected components.

If $\mathbf{A}$ is the disjoint union of strongly connected components, then
we create a matrix that witnesses the balancedness of the relation of
$\mathbf{A}$. Consider any edge $(u,v)$ of $\mathbf{A}$. Take the cycle formed
by $(u,v)$ together with the path from $v$ to $u$. Add all of these edges to
the matrix as columns. The resulting matrix contains each edge at least once;
furthermore every vertex appears the same number of times in the first and the
second row (since the edges form cycles). Thus $\mathbf{A}$ is balanced. ∎