# CLAP: A New Algorithm for Promise CSPs††thanks: An extended abstract of this
work appeared in the Proceedings of the 2022 ACM-SIAM Symposium on Discrete
Algorithms (SODA’22) [32]. The research leading to these results has received
funding from the European Research Council (ERC) under the European Union’s
Horizon 2020 research and innovation programme (grant agreement No 714532).
Stanislav Živný was supported by a Royal Society University Research
Fellowship. The paper reflects only the authors’ views and not the views of
the ERC or the European Commission. The European Union is not liable for any
use that may be made of the information contained therein. This work was also
supported by UKRI EP/X024431/1. 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.

Lorenzo Ciardo Department of Computer Science, University of Oxford, UK.
Stanislav Živný†

(3rd September 2024)

###### Abstract

We propose a new algorithm for Promise Constraint Satisfaction Problems
(PCSPs). It is a combination of the Constraint Basic LP relaxation and the
Affine IP relaxation ($\operatorname{CLAP}$). We give a characterisation of
the power of $\operatorname{CLAP}$ in terms of a minion homomorphism. Using
this characterisation, we identify a certain weak notion of symmetry which, if
satisfied by infinitely many polymorphisms of PCSPs, guarantees tractability.

We demonstrate that there are PCSPs solved by $\operatorname{CLAP}$ that are
not solved by any of the existing algorithms for PCSPs; in particular, not by
the $\operatorname{BLP}+\operatorname{AIP}$ algorithm of Brakensiek et al.
[SICOMP’20] and not by a reduction to tractable finite-domain CSPs.

##  1 Introduction

#### Constraint Satisfaction

Constraint Satisfaction Problems (CSPs) have driven some of the most
influential developments in theoretical computer science, from NP-completeness
to the PCP theorem [2, 1, 39] to semidefinite programming algorithms [63] to
the Unique Games Conjecture [53].

A CSP over domain $A$ is specified by a finite collection $\mathbf{A}$ of
relations over $A$, and is denoted by $\operatorname{CSP}(\mathbf{A})$. Given
on input a set of variables and a set of constraints, each of which uses
relations from $\mathbf{A}$, the task is to decide the existence of an
assignment of values from $A$ to the variables that satisfies all the
constraints. Classic examples of CSPs include $2$-SAT, graph $3$-colouring,
and linear equations of fixed width over finite groups.

For Boolean CSPs, which are CSPs with $|A|=2$, Schaefer proved that every such
CSP is either solvable in polynomial time or is NP-complete [65]. Feder and
Vardi famously conjectured that the same holds true for CSPs over arbitrary
finite domains [41]. Furthermore, they realised the importance of considering
closure properties of solution spaces of CSPs [41], which initiated the
algebraic approach [50, 49, 26]. The key notion in the algebraic approach is
that of _polymorphisms_ , which are operations that take solutions to a CSP
and are guaranteed to return, by a coordinatewise application, a solution to
the same CSP. All CSPs admit projections (also known as dictators) as
polymorphisms. However, the presence of less trivial polymorphisms, satisfying
some notion of symmetry, is necessary for tractability. For instance, the set
of solutions to $2$-SAT is closed under the ternary majority operation
$\operatorname{maj}:\\{0,1\\}^{3}\to\\{0,1\\}$ that satisfies the following
notion of symmetry:
$\operatorname{maj}(a,a,b)=\operatorname{maj}(a,b,a)=\operatorname{maj}(b,a,a)=a$
for any $a,b\in\\{0,1\\}$. Similarly, the set of solutions to Horn-SAT is
closed under the binary minimum operation $\min:\\{0,1\\}^{2}\to\\{0,1\\}$
that satisfies a different notion of symmetry: $\min(a,a)=a$,
$\min(a,b)=\min(b,a)$, and $\min(a,\min(b,c))=\min(\min(a,b),c)$ for any
$a,b,c\in\\{0,1\\}$. The binary $\max$ operation – which is a polymorphism of
dual Horn-SAT – has the same notion of symmetry, called semilattice [11].
Together with the ternary minority polymorphism, which captures linear
equations on $\\{0,1\\}$, this gives all non-trivial tractable cases from
Schaefer’s dichotomy result.111The trivial cases, called $0$\- and $1$-valid,
are captured by the constant-$0$ and constant-$1$ polymorphisms, respectively.

The polymorphisms of any CSP form a clone, in that they include all
projections and are closed under composition. For instance, since Horn-SAT has
$\min$ as a polymorphism, it also has the $4$-ary minimum operation
$\min_{4}(a,b,c,d)=\min(a,\min(b,\min(c,d)))$ as a polymorphism. Building on
the connection to universal algebra, the algebraic approach has been
tremendously successful beyond decision CSPs, e.g. for robust satisfiability
of CSPs [36, 10, 35], for exact optimisation of CSPs [57, 66, 54], and for
characterising the power of algorithms [59, 9, 14, 55, 56, 67, 68]. The
culmination of the algebraic approach is the positive resolution of the
dichotomy conjecture by Bulatov [28] and Zhuk [71]. We refer the reader to
[11] for a survey on the algebraic approach.

#### Promise Constraint Satisfaction

In this paper, we study Promise Constraint Satisfaction Problems (PCSPs),
whose systematic study was initiated by Austrin, Guruswami, and Håstad [5],
and Brakensiek and Guruswami [20]. PCSPs form a vast generalisation of CSPs.
In $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, each constraint comes in two
forms, a strict one in $\mathbf{A}$ and a weak one in $\mathbf{B}$. The goal
is to distinguish between (i) the case in which (the strong form of) the
constraints can be simultaneously satisfied in $\mathbf{A}$ and (ii) the case
in which (even the weak form of) the constraints cannot be simultaneously
satisfied in $\mathbf{B}$. The promise is that it is never the case that the
PCSP is not satisfiable in the strict sense but is satisfiable in the weak
sense. If the strict and weak forms coincide in every constraint (i.e., if
$\mathbf{A}=\mathbf{B}$) we get the (non-promise) CSPs. However, PCSPs include
many fundamental problems that are inexpressible as CSPs.

The simplest example of strict vs. weak constraints is when the weak
constraints are supersets of the strict constraints on the same domain (the
first two examples below) or on a larger domain (the third example below); the
notion of homomorphism from $\mathbf{A}$ to $\mathbf{B}$ formalises this for
any PCSP.

First, can we distinguish a $g$-satisfiable $k$-SAT instance (in the sense
that there is an assignment that satisfies at least $g$ literals in each
clause) from an instance that is not even $1$-satisfiable? This problem was
studied in [5], where it was shown to be solvable in polynomial time if
$\frac{g}{k}\geq\frac{1}{2}$ and NP-complete otherwise. Recently, this result
has been generalised to arbitrary finite domains [23].

Second, can we distinguish a $3$-SAT formula that admits an assignment
satisfying exactly $1$ literal in each clause (i.e., a satisfiable instance of
$\mathbf{1}\textbf{-in-}\mathbf{3}$-SAT) from one that does not admit an
assignment satisfying $1$ or $2$ literals in each clause (i.e., a non-
satisfiable instance of Not-All-Equal-$3$-SAT)? Remarkably, while both
$\mathbf{1}\textbf{-in-}\mathbf{3}$ and $\mathbf{NAE}$ are NP-hard, this
promise version is solvable in polynomial time [20, 19].

Third, can we distinguish a $k$-colourable graph from a graph that is not even
$\ell$-colourable, where $k\leq\ell$? This is the _approximate graph
colouring_ problem, which is believed to be NP-hard for any fixed $3\leq
k\leq\ell$, but has been elusive since the 1970s [43]. In particular, the
larger the gap is between $k$ and $\ell$ the easier the problem could in
principle be and, thus, the more challenging it is to prove NP-hardness. The
current state of the art is NP-hardness for $k=3$ and $\ell=5$ [8], while
already the case of $k=3$ and $\ell=6$ is open. For any $k\geq 4$ and
$\ell=\ell(k)=\binom{k}{\lfloor k\rfloor/2}-1$, NP-hardness has been
established in [70].

While a systematic study of PCSPs was initiated only recently [5, 20],
concrete PCSPs have been considered for a while, e.g. approximate graph [43,
69, 16, 51, 52, 44] and hypergraph colouring [40]. A highlight result is the
dichotomy of Boolean symmetric PCSPs [42] (in which all constraint relations
are symmetric), following an earlier classification of Boolean symmetric PCSPs
with disequalities [20]. Very recent works have investigated certain Boolean
non-symmetric PCSPs [24] and certain non-Boolean symmetric PCSPs [7]. Other
recent results include, e.g., [4, 45, 21].

Most of the recent progress, including results on the approximate graph
colouring problem [8, 70] and on the approximate graph homomorphism problem
[58, 70], rely on the algebraic approach to PCSPs [8]. In particular, the
breakthrough results in [8], building on [12], established that the complexity
of PCSPs is captured by the polymorphism minions and certain types of
symmetries these minions satisfy – these are non-nested identities on
polymorphisms, such as the majority example but not the semilattice example.
Crucially, minions are less structured than clones: A minion (of functions) is
a set of operations closed under permuting coordinates, identifying
coordinates, and introducing dummy coordinates, but not under
composition.222In this work, we shall use the more abstract notion of minion
introduced in [22], cf. Definition 6. Thus, unlike in our earlier CSP example
(corresponding to Horn-SAT), a binary minimum polymorphism of a PCSP cannot in
general be used to generate a $4$-ary minimum polymorphism of the same PCSP.

Despite the momentous results in [8], there is a long way to go to classify
all PCSPs, and it is not even clear whether a dichotomy for all PCSPs should
be expected. When Feder and Vardi conjectured a CSP dichotomy [41], the
Boolean case [65] and the graph case [46] had been fully classified. We seem
quite far from these two cases being classified for PCSPs. Thus, further
progress is needed on both the hardness and tractability part. This paper
focusses on the latter.

#### Finite tractability

Although PCSPs are (much) more general than CSPs, some PCSPs can be reduced to
tractable CSPs. This idea was introduced in [19] under the name of homomorphic
sandwiching (cf. Section 2 for a precise definition); PCSPs that are reducible
to tractable (finite-domain) CSPs are called _finitely tractable_. Finite
tractability is not sufficient to explain tractability of all tractable PCSPs.
In particular, Barto et al. [8] showed that the above-mentioned example
$\mathbf{1}\textbf{-in-}\mathbf{3}$ vs. $\mathbf{NAE}$ is not finitely
tractable, despite being a tractable PCSP [20]. We remark that it is not
inconceivable (and in fact was conjectured in [19]) that every tractable
(finite-domain) PCSP could be reducible to a tractable CSP possibly over an
infinite domain; this is the case for the $\mathbf{1}\textbf{-in-}\mathbf{3}$
vs. $\mathbf{NAE}$ problem [19]. However, while certain infinite-domain CSPs
are amenable to algebraic methods, the complexity of infinite-domain CSPs is
far from understood, cf. [17, 18, 13] for recent work.

Since finite tractability does not capture all tractable PCSPs, there is need
for other algorithmic tools. One possibility is to attempt to extend
algorithmic techniques developed for CSPs.

There are two main algorithmic approaches to CSPs. On the one hand, there are
local consistency methods [41], which have been studied in theoretical
computer science but also in artificial intelligence, logic, and database
theory. The power of local consistency for CSPs has been characterised in [25,
9], and it is known that the third level of consistency solves all so-called
bounded-width CSPs [6]. On the other hand, there are CSPs solvable by
algorithms based on generalisations of Gaussian elimination, most notably CSPs
with a Mal’tsev polymorphism [29]. This method has been pushed to its limit,
in a way, in [48, 14]. While the NP-hardness part of the CSP dichotomy has
been known since [26], the challenge in proving the algorithmic part is the
complicated interaction of these two very different algorithmic approaches.
Although this interaction does not occur in Boolean CSPs, it occurs already in
CSPs on three-element domains [27].

The characterisation of the power of the first level of the consistency
methods, $1$-consistency (also known as arc-consistency [61]), has been lifted
from CSPs [41] to PCSPs in [8]. Rather than establishing $1$-consistency
combinatorially, one can employ convex relaxations.

#### Relaxations

A canonical analogue of $1$-consistency is the _basic linear programming
relaxation_ ($\operatorname{BLP}$) [59], which in fact is stronger than
$1$-consistency [60]. The characterisation of the power of
$\operatorname{BLP}$ has been lifted from CSPs [59] to PCSPs in [8], both in
terms of a minion and a property of polymorphisms. The power of
$\operatorname{BLP}$ is captured by a minion consisting of rational stochastic
vectors333A vector is _stochastic_ if its entries are nonnegative and sum up
to one. or, equivalently, by the presence of symmetric polymorphisms of all
arities; these are polymorphisms invariant under any permutation of the
coordinates. For example, we have seen that Horn-SAT, a classic CSP, has a
binary symmetric polymorphism, namely $\min$. We have also seen that $\min$
can generate a $4$-ary operation $\min_{4}$, which is symmetric. Similarly,
$\min$ can generate (via composition) symmetric operations of all arities, and
thus Horn-SAT is solved by $\operatorname{BLP}$.

A different relaxation of PCSPs is the _basic affine integer programming
relaxation_ ($\operatorname{AIP}$) [19]. The power of $\operatorname{AIP}$ has
been characterised, both in terms of a minion and a property of polymorphisms,
in [8]. The minion capturing $\operatorname{AIP}$ consists of integer affine
vectors.444An integer vector is _affine_ if its entries sum up to one.
Concerning polymorphisms, $\operatorname{AIP}$ is captured by polymorphisms of
all odd arities that are invariant under permutations that only permute odd
and even coordinates separately, and additionally satisfy that adjacent
coordinates cancel each other out. The $\mathbf{1}\textbf{-in-}\mathbf{3}$ vs.
$\mathbf{NAE}$ problem is solved by $\operatorname{AIP}$ (cf. Example 5).

Brakensiek et al. [22] proposed a combination of the two above-mentioned
relaxations, called $\operatorname{BLP}+\operatorname{AIP}$. Their algorithm
has many interesting features. Firstly, it solves PCSPs that admit only
infinitely many symmetric polymorphisms (i.e., not all arities are required as
in the case of $\operatorname{BLP}$). Secondly, it solves all tractable
Boolean CSPs, thus demonstrating how research on PCSPs can shed new light on
(non-promise) CSPs. In fact, [22] established the power of
$\operatorname{BLP}+\operatorname{AIP}$ in terms of a minion and (a property
of) polymorphisms. The minion capturing
$\operatorname{BLP}+\operatorname{AIP}$ is essentially a product of the
$\operatorname{BLP}$ and $\operatorname{AIP}$ minions [22]. Concerning
polymorphisms, $\operatorname{BLP}+\operatorname{AIP}$ is captured by
polymorphisms of all odd arities that are invariant under permutations that
only permute odd and even coordinates.

It may be that $\operatorname{BLP}+\operatorname{AIP}$ is the only algorithm
needed to solve all tractable _Boolean_ PCSPs. However, as already observed in
[22], $\operatorname{BLP}+\operatorname{AIP}$ does not solve some rather
simple, tractable, _non-Boolean_ PCSPs. Motivated by this, we investigate
algorithms that are stronger than $\operatorname{BLP}+\operatorname{AIP}$. We
note that all PCSPs hitherto known to be tractable are solved by
$\operatorname{BLP}+\operatorname{AIP}$ or by finite tractability (i.e., by a
reduction to a tractable finite-domain CSP). In this work, we provide an
example of a PCSP that is tractable (through our algorithm) but is not solved
by either of those two algorithmic techniques.

#### Contributions

Building on the work of Brakensiek et al. [22], we study stronger relaxations
for PCSPs and give three main contributions.

(1) CLAP Our first contribution is the introduction of $\operatorname{CLAP}$
to the study of PCSPs. Our goal was to design an algorithm that, unlike
$\operatorname{BLP}+\operatorname{AIP}$, solves all CSPs of bounded width.
While all bounded-width CSPs can be solved by $3$-consistency [6], and thus
also by the third level of the Sherali-Adams hierarchy for
$\operatorname{BLP}$ (e.g., by [67]), Kozik showed that already (a special
case of) the singleton arc-consistency ($\operatorname{SAC}$) algorithm,
introduced in [38] (cf. [15, 30]), solves all bounded-width CSPs [56]. Thus,
we study the LP relaxation that we call the _singleton_ $\operatorname{BLP}$
($\operatorname{SBLP}$), which is at least as strong as $\operatorname{SAC}$.
A special case of $\operatorname{SBLP}$ (without this name) implicitly
appeared in the literature, e.g. in [5, 20] for Boolean PCSPs. The idea behind
$\operatorname{SBLP}$ is essentially to run $\operatorname{SAC}$ but replace
the arc-consistency check by the $\operatorname{BLP}$; i.e., the algorithm
repeatedly takes a variable-value pair $(x,a)$ and tests the feasibility of
the $\operatorname{BLP}$ with the requirement that $x$ should be assigned the
value $a$. If this LP is infeasible then $a$ is removed from the domain of
$x$. This is repeated until convergence. If any variable ends up with an empty
domain then $\operatorname{SBLP}$ rejects, otherwise it accepts. Overall, the
number of $\operatorname{BLP}$ calls occurring for an instance of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ with variable-set $X$ is at most
polynomial in the size of $X$. As mentioned above, this simple algorithm
solves all bounded-width CSPs [56].

We adopt a modification of $\operatorname{SBLP}$ that turns out to be more
naturally captured by a minion-oriented analysis: the _constraint_
$\operatorname{BLP}$ ($\operatorname{CBLP}$). This (possibly) stronger
algorithm is a generalisation of $\operatorname{SBLP}$ in which we do not
consider only variable-value pairs $(x,a)$, but rather the constraint-
assignment pairs $(\mathbf{x},\mathbf{a})$ for every constraint in the
instance. As in $\operatorname{SBLP}$, if fixing a (local) assignment to a
constraint yields an infeasible $\operatorname{BLP}$ then the assignment is
removed from the constraint relation. Upon convergence, which takes at most
polynomially many $\operatorname{BLP}$ calls, if any constraint ends up with
an empty relation then $\operatorname{CBLP}$ rejects, otherwise it accepts.

Our algorithm $\operatorname{CLAP}$ first runs $\operatorname{CBLP}$ and then,
upon termination, refines the solutions of $\operatorname{CBLP}$ by running
(essentially) $\operatorname{AIP}$. If one believes the suggestion in [22]
that constantly many rounds of the Sherali-Adams hierarchy for
$\operatorname{BLP}+\operatorname{AIP}$ could solve all tractable (non-
promise) CSPs, then it is not outrageous to believe that the same could be
true for $\operatorname{CLAP}$, and $\operatorname{CLAP}$ might be easier to
analyse than such an algorithm.

(2) Characterisation Our second contribution is a minion characterisation of
the power of $\operatorname{CLAP}$, stated as Theorem 13. The objects in the
minion are essentially matrices with a particular structure, which we call
skeletal (cf. Definition 11). These matrices capture the $\operatorname{CBLP}$
part of $\operatorname{CLAP}$ and together with certain integer affine vectors
form the minion (cf. Definition 12). Another, more conceptual contribution is
the introduction of a minion of matrices to the study of PCSPs.

(3) H-symmetric polymorphisms The minion characterisation is crucial to our
third contribution: the identification of a sufficient condition for
$\operatorname{CLAP}$ to work in terms of the symmetries of the polymorphisms.
This is stated as Theorem 15, using the notion of $H$-symmetry. This condition
can be more easily checked for concrete templates, thus allowing us to design
a separating example that is not finitely tractable and is not solved by
$\operatorname{BLP}+\operatorname{AIP}$ (nor by local consistency methods, see
[3]), but is solved by $\operatorname{CLAP}$. It follows that our new
algorithm is strictly more powerful than
$\operatorname{BLP}+\operatorname{AIP}$ (and separated by an interesting PCSP
that is not reducible to a tractable finite-domain CSP via “gadget
reductions”, which capture the algebraic approach to PCSPs [8]).

For a matrix $H$, a polymorphism $f$ is $H$-symmetric if $f$ is invariant
under permutations of the coordinates but only on a specific set of inputs
determined by $H$ (cf. Definition 14). For instance, if $H$ is a row vector
then we obtain the requirement that $f$ be symmetric on all inputs. If $H$ is
the identity matrix then we require that $f$ be symmetric only on inputs in
which different entries occur with different multiplicities. In general, the
intuition is that we capture ‘symmetry with exceptions that depend on
multiplicities’. We refer the reader to the discussion in Section 3 for
details.

After necessary background material in Section 2, our algorithm
$\operatorname{CLAP}$ and the main results are presented in Section 3; the
proofs appear in Sections 4 and 5.

##  2 Preliminaries

We let $\mathbb{N}=\\{1,2,\ldots\\}$ and
$\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}$. The cardinality of $\mathbb{N}$ shall
be denoted by $\aleph_{0}$. For $k\in\mathbb{N}$, $[k]$ denotes the set
$\\{1,\ldots,k\\}$. For a set $A$, $\operatorname{\mathcal{P}}(A)$ denotes the
set of all subsets of $A$. We denote by $\leq_{p}$ many-one polynomial-time
reductions. We shall use standard notation for vectors and matrices. Vectors
will be treated as column vectors and whenever convenient identified with the
corresponding (row) tuples. Both tuples and vectors will be typed in bold
font. We denote by $\mathbf{e}_{i}$ the $i$-th standard unit vector of the
appropriate size (which will be clear from the context); i.e.,
$\mathbf{e}_{i}$ is equal to $1$ in the $i$-th coordinate and $0$ elsewhere.
We denote by $\mathbf{0}_{p}$ and by $\mathbf{1}_{p}$ the all-zero and all-one
vector, respectively, of size $p$; if the size is clear, we occasionally drop
the subscript. The _support_ of a vector $\mathbf{v}=(v_{i})$ of size $p$ is
the set $\operatorname{supp}(\mathbf{v})=\\{i\in[p]:v_{i}\neq 0\\}$. $I_{p}$
denotes the identity matrix of order $p$, while $O$ denotes an all-zero matrix
of suitable size.

#### Promise CSPs

A _signature_ $\sigma$ is a finite set of relation symbols $R$, each with its
arity $\operatorname{ar}(R)\in\mathbb{N}$. A _relational structure_ over a
signature $\sigma$, or a $\sigma$-structure, is a finite universe $A$, called
the _domain_ of $\mathbf{A}$, and a relation $R^{\mathbf{A}}\subseteq
A^{\operatorname{ar}(R)}$ for each symbol $R\in\sigma$. For two
$\sigma$-structures $\mathbf{A}$ and $\mathbf{B}$, a mapping $f:A\to B$ is
called a _homomorphism_ from $\mathbf{A}$ to $\mathbf{B}$, denoted by
$f:\mathbf{A}\to\mathbf{B}$, if $f$ preserves all relations; that is, for
every $R\in\sigma$ and every tuple $\textbf{a}\in R^{\mathbf{A}}$, we have
$f(\textbf{a})\in R^{\mathbf{B}}$, where $f$ is applied coordinatewise. The
existence of a homomorphism from $\mathbf{A}$ to $\mathbf{B}$ is denoted by
$\mathbf{A}\to\mathbf{B}$. A PCSP _template_ is a pair
$(\mathbf{A},\mathbf{B})$ of relational structures over the same signature
such that $\mathbf{A}\to\mathbf{B}$. Without loss of generality, we will often
assume that $A$, the domain of $\mathbf{A}$, is $[n]$.

######  Definition 1.

Let $(\mathbf{A},\mathbf{B})$ be a PCSP template. The _decision version_ of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is the following problem: Given
as input a relational structure $\mathbf{X}$ over the same signature as
$\mathbf{A}$ and $\mathbf{B}$, output Yes if $\mathbf{X}\to\mathbf{A}$ and No
if $\mathbf{X}\not\to\mathbf{B}$. The _search version_ of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is the following problem: Given
as input a relational structure $\mathbf{X}$ over the same signature as
$\mathbf{A}$ and $\mathbf{B}$ and such that $\mathbf{X}\to\mathbf{A}$, find a
homomorphism from $\mathbf{X}$ to $\mathbf{B}$.

For a relational structure $\mathbf{A}$, the _constraint satisfaction problem_
(CSP) with template $\mathbf{A}$ [41], denoted by
$\operatorname{CSP}(\mathbf{A})$, is
$\operatorname{PCSP}(\mathbf{A},\mathbf{A})$.

######  Example 2.

For $k\geq 2$, let $\mathbf{K}_{k}$ be the structure with domain $[k]$ and a
binary relation $\\{(i,j)\in[k]^{2}\mid i\neq j\\}$. Then,
$\operatorname{CSP}(\mathbf{K}_{k})$ is the standard graph $k$-colouring
problem. For $k\leq\ell$,
$\operatorname{PCSP}(\mathbf{K}_{k},\mathbf{K}_{\ell})$ is the _approximate
graph colouring problem_ [43]. In the decision version, the task is to decide
whether a graph is $k$-colourable or not even $\ell$-colourable. In the search
version, given a $k$-colourable graph $G$, the task is to find an
$\ell$-colouring of $G$. It is widely believed that for any fixed $3\leq
k\leq\ell$, $\operatorname{PCSP}(\mathbf{K}_{k},\mathbf{K}_{\ell})$ is NP-
hard; i.e., constantly many colours do not help. The current most general NP-
hardness result is known for $k=3$ and $\ell=5$ by Bulín, Krokhin, and Opršal
[8] and for $k\geq 4$ and $\ell=\ell(k)=\binom{k}{\lfloor k\rfloor/2}-1$ by
Wrochna and Živný [70].

We call a PCSP template $(\mathbf{A},\mathbf{B})$ _tractable_ if any instance
of $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ can be solved in polynomial
time in the size of the input structure $\mathbf{X}$. It is easy to show that
the decision version reduces to the search version [8] (but the converse is
not known in general); for CSPs, the two versions are equivalent [33, 26]. Our
results are for the decision version.

######  Example 3.

Let $\mathbf{1}\textbf{-in-}\mathbf{3}$ be the Boolean structure with domain
$\\{0,1\\}$ and a single ternary relation $\\{(0,0,1),(0,1,0),(1,0,0)\\}$. Let
$\mathbf{NAE}$ be the structure with domain $\\{0,1\\}$ and a single ternary
relation $\\{0,1\\}^{3}\setminus\\{(0,0,0),(1,1,1)\\}$. Then,
$\operatorname{CSP}(\mathbf{1}\textbf{-in-}\mathbf{3})$ is the (positive)
$1$-in-$3$-SAT problem and $\operatorname{CSP}(\mathbf{NAE})$ is the
(positive) Not-All-Equal-$3$-SAT problem. Since both of these problems are NP-
hard [65], the PCSP templates
$(\mathbf{1}\textbf{-in-}\mathbf{3},\mathbf{1}\textbf{-in-}\mathbf{3})$ and
$(\mathbf{NAE},\mathbf{NAE})$ are both intractable. However, the PCSP template
$(\mathbf{1}\textbf{-in-}\mathbf{3},\mathbf{NAE})$ is tractable, as shown by
Brakensiek and Guruswami [20].

######  Definition 4.

Let $(\mathbf{A},\mathbf{B})$ be a PCSP template with signature $\sigma$. An
operation $f:A^{L}\to B$, where $L\in\mathbb{N}$, is a _polymorphism_ of arity
$L$ of $(\mathbf{A},\mathbf{B})$ if for every $R\in\sigma$ of arity
$k=\operatorname{ar}(R)$ and for any possible $L\times k$ matrix whose rows
are tuples in $R^{\mathbf{A}}$, the application of $f$ on the columns of the
matrix gives a tuple in $R^{\mathbf{B}}$. We denote by
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ the set of all polymorphisms of
$(\mathbf{A},\mathbf{B})$.

######  Example 5.

The unary operation $\neg:\\{0,1\\}\to\\{0,1\\}$ defined by $\neg(a)=1-a$ is a
polymorphism of $(\mathbf{NAE},\mathbf{NAE})$ but not a polymorphism of
$(\mathbf{1}\textbf{-in-}\mathbf{3},\mathbf{1}\textbf{-in-}\mathbf{3})$. For
any odd $L$, the $L$-ary operation $f:\\{0,1\\}^{L}\to\\{0,1\\}$ defined by
$f(a_{1},\ldots,a_{L})=1$ if $a_{1}-a_{2}+a_{3}-\cdots+a_{L}>0$ and
$f(a_{1},\ldots,a_{L})=0$ otherwise is a polymorphism of
$(\mathbf{1}\textbf{-in-}\mathbf{3},\mathbf{NAE})$.

#### Minions

Polymorphisms of CSPs form clones; i.e.,
$\operatorname{Pol}(\mathbf{A},\mathbf{A})$ contains all projections (also
known as dictators) and is closed under composition [11]. Polymorphisms of the
(more general) PCSPs form _minions_ ; i.e, they are closed under taking
minors.555We remark that clones are also closed under taking minors. Formally,
given an $L$-ary function $f:A^{L}\to B$, its _minor_ relative to a map
$\pi:[L]\to[L^{\prime}]$ is the $L^{\prime}$-ary function
$f_{/\pi}:A^{L^{\prime}}\to B$ defined by

$\displaystyle
f_{/\pi}(a_{1},\ldots,a_{L^{\prime}})=f(a_{\pi(1)},\ldots,a_{\pi(L)}).$ (1)

Equivalently, a minor of $f$ is a function obtained from $f$ by identifying
variables, permuting variables, and introducing dummy variables. Rather than
focussing on minions of functions, we consider here abstract minions, as
described and used in [22].

######  Definition 6.

A _minion_ $\mathscr{M}$ consists in the disjoint union of sets
$\mathscr{M}^{(L)}$ for $L\in\mathbb{N}$ equipped with operations
$(\cdot)_{/\pi}:\mathscr{M}^{(L)}\rightarrow\mathscr{M}^{(L^{\prime})}$ for
all functions $\pi:[L]\rightarrow[L^{\prime}]$, which satisfy

  * •

$(M_{/\pi})_{/\tilde{\pi}}=M_{/\tilde{\pi}\circ\pi}$ for
$\pi:[L]\rightarrow[L^{\prime}]$,
$\tilde{\pi}:[L^{\prime}]\rightarrow[L^{\prime\prime}]$ and

  * •

$M_{/\operatorname{id}}=M$

for all $M\in\mathscr{M}^{(L)}$.

######  Definition 7.

For two minions $\mathscr{M}$ and $\mathscr{N}$, a _minion homomorphism_
$\xi:\mathscr{M}\rightarrow\mathscr{N}$ is a map that preserves arities and
minors: Given $M\in\mathscr{M}^{(L)}$ and $\pi:[L]\rightarrow[L^{\prime}]$,
$\xi(M)\in\mathscr{N}^{(L)}$ and $\xi(M_{/\pi})=\xi(M)_{/\pi}$.

For any PCSP template $(\mathbf{A},\mathbf{B})$, the set
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ of its polymorphisms equipped with
the operations described by (1) is a minion [8]. One of the results in [8]
established that minion homomorphisms give rise to polynomial-time reductions:
If there is a minion homomorphism from
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ to
$\operatorname{Pol}(\mathbf{A}^{\prime},\mathbf{B}^{\prime})$, then
$\operatorname{PCSP}(\mathbf{A}^{\prime},\mathbf{B}^{\prime})\leq_{p}\operatorname{PCSP}(\mathbf{A},\mathbf{B})$.
Minions are also useful for characterising the power of algorithms, as we will
discuss later.

######  Remark 8.

Although we will not use this categorical view, we remark that a minion is
nothing but a functor from the category of nonempty finite sets to the
category of nonempty sets, and a minion homomorphism is a natural
transformation.

#### Existing algorithms

One way to establish tractability of PCSPs is to reduce to CSPs. Let
$(\mathbf{A},\mathbf{B})$ be a PCSP template. A structure $\mathbf{C}$ is
called a (homomorphic) _sandwich_ if $\mathbf{A}\to\mathbf{C}\to\mathbf{B}$.
It is known that, in this case,
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})\leq_{p}\operatorname{CSP}(\mathbf{C})$.666This
is a special case of homomorphic relaxation [8], which we do not need here.
Thus, if $\mathbf{C}$ is a tractable CSP template then
$(\mathbf{A},\mathbf{B})$ is a tractable PCSP template. If $\mathbf{C}$ has a
finite domain, we say that $(\mathbf{A},\mathbf{B})$ is _finitely tractable_.

######  Example 9.

The PCSP template $(\mathbf{1}\textbf{-in-}\mathbf{3},\mathbf{NAE})$ from
Example 3 is tractable [20] but not finitely tractable unless P=NP, as shown
in [8].

Another way to establish tractability for PCSPs is to leverage convex
relaxations. In Section 1, we mentioned three studied relaxations:
$\operatorname{BLP}$ [59], $\operatorname{AIP}$ [20], and
$\operatorname{BLP}+\operatorname{AIP}$ [22]. Their powers have been
characterised in [8, 22] in terms of certain minions and polymorphism
identities. The details of these relaxations and the characterisations are
provided in Appendix A.

All PCSPs hitherto known to be tractable are solved by finite tractability
(i.e., by a reduction to a tractable finite-domain CSP) or by
$\operatorname{BLP}+\operatorname{AIP}$. The next example identifies a simple
PCSP template not captured by either of these two methods.

######  Example 10.

Consider the relational structures
$\mathbf{A}=(A;R_{1}^{\mathbf{A}},R_{2}^{\mathbf{A}})$ and
$\mathbf{B}=(B;R_{1}^{\mathbf{B}},R_{2}^{\mathbf{B}})$ on the domain
$A=B=\\{0,\ldots,6\\}$ with the following relations:
$R_{1}^{\mathbf{A}}=\\{(0,0,1),(0,1,0),(1,0,0)\\}$ is
$\mathbf{1}\textbf{-in-}\mathbf{3}$ on $\\{0,1\\}$,
$R_{1}^{\mathbf{B}}=\\{0,1\\}^{3}\setminus\\{(0,0,0),(1,1,1)\\}$ is
$\mathbf{NAE}$ on $\\{0,1\\}$, and
$R_{2}^{\mathbf{A}}=R_{2}^{\mathbf{B}}=\\{(2,3),(3,2),(4,5),(5,6),(6,4)\\}$.
The identity mapping is a homomorphism from $\mathbf{A}$ to $\mathbf{B}$, so
$(\mathbf{A},\mathbf{B})$ is a PCSP template. Since the directed graph
corresponding to $R_{2}^{\mathbf{A}}=R_{2}^{\mathbf{B}}$ is a disjoint union
of a directed $2$-cycle and a directed $3$-cycle, [22, Example 6.1] shows that
the $\operatorname{BLP}+\operatorname{AIP}$ algorithm does not solve
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$. We claim that the template
($\mathbf{A},\mathbf{B}$) is not finitely tractable. For contradiction, assume
that there is a finite relational structure
$\mathbf{C}=(C;R_{1}^{\mathbf{C}},R_{2}^{\mathbf{C}})$ such that
$\mathbf{A}\rightarrow\mathbf{C}\rightarrow\mathbf{B}$ and
$\operatorname{CSP}(\mathbf{C})$ is tractable. We will argue that this would
imply finite tractability of
$(\mathbf{1}\textbf{-in-}\mathbf{3},\mathbf{NAE})$, which contradicts the
result in [8] (unless P=NP); cf. Example 9. Indeed, the existence of such
$\mathbf{C}$ gives the following chain of homomorphisms:

$\displaystyle\mathbf{1}\textbf{-in-}\mathbf{3}=(\\{0,1\\};R_{1}^{\mathbf{A}})\rightarrow(A;R_{1}^{\mathbf{A}})\rightarrow(C;R_{1}^{\mathbf{C}})\rightarrow(B;R_{1}^{\mathbf{B}})\rightarrow(\\{0,1\\};R_{1}^{\mathbf{B}})=\mathbf{NAE}$
(2)

where the first map is the inclusion of $\\{0,1\\}$ in $A$, the second and the
third are the maps witnessing
$\mathbf{A}\rightarrow\mathbf{C}\rightarrow\mathbf{B}$, and the fourth is any
map $g:B\rightarrow\\{0,1\\}$ such that $g(0)=0$ and $g(1)=1$. Let
$\tilde{\mathbf{C}}=(C;R_{1}^{\mathbf{C}})$. Observe that $\tilde{\mathbf{C}}$
is tractable since the inclusion map gives a minion homomorphism
$\operatorname{Pol}(\mathbf{C},\mathbf{C})\rightarrow\operatorname{Pol}(\tilde{\mathbf{C}},\tilde{\mathbf{C}})$,
and thus
$\operatorname{CSP}(\tilde{\mathbf{C}})=\operatorname{PCSP}(\tilde{\mathbf{C}},\tilde{\mathbf{C}})\leq_{p}\operatorname{PCSP}(\mathbf{C},\mathbf{C})=\operatorname{CSP}(\mathbf{C})$
by [8, Theorem 3.1]. This proves the claim, as (2) established
$\mathbf{1}\textbf{-in-}\mathbf{3}\rightarrow\tilde{\mathbf{C}}\rightarrow\mathbf{NAE}$.

Notice that the assignment $f\mapsto g\circ f|_{\\{0,1\\}^{L}}$ (where $f$ is
a polymorphism of $(\mathbf{A},\mathbf{B})$ of arity $L$ and $g$ is the map
considered above) yields a minion homomorphism from
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ to
$\operatorname{Pol}(\mathbf{1}\textbf{-in-}\mathbf{3},\mathbf{NAE})$. As
established in [3, Corollary 4.2], the template
$(\mathbf{1}\textbf{-in-}\mathbf{3},\mathbf{NAE})$ does not have bounded width
– i.e., is not solved by local consistency methods. It follows from [8, Lemma
7.5] that $(\mathbf{A},\mathbf{B})$ does not have bounded width either.

The template from Example 10 will be proved tractable later (in Example 16)
using our new algorithm, which we will present next.

##  3 The CLAP algorithm

Let $(\mathbf{A},\mathbf{B})$ be a PCSP template with signature $\sigma$ and
let $\mathbf{X}$ be an instance of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$. Without loss of generality, we
assume that $\sigma$ contains a unary symbol $R_{\operatorname{u}}$ such that
$R_{\operatorname{u}}^{\mathbf{X}}=X$, $R_{\operatorname{u}}^{\mathbf{A}}=A$,
and $R_{\operatorname{u}}^{\mathbf{B}}=B$. If this is not the case, the
signature and the instance can be extended without changing the set of
solutions. Our algorithm – the combined CBLP+AIP algorithm
($\operatorname{CLAP}$), presented in Algorithm 1 and discussed below – builds
on $\operatorname{BLP}$ [8] and $\operatorname{BLP}+\operatorname{AIP}$ [22].

$\operatorname{CLAP}$ works in two stages. In the first stage, it runs
$\operatorname{CBLP}$; i.e., a modified version of the singleton arc-
consistency algorithm (cf. [38]) where $(i)$ the “arc-consistency” part is
replaced by $\operatorname{BLP}$, and $(ii)$ the “singleton” part is boosted
by requiring that every constraint-assignment pair (as opposed to every
variable-value pair) is fixed at each iteration. In the second stage, it
refines $\operatorname{CBLP}$ by doing an additional sanity check: At least
one of the solutions computed by $\operatorname{CBLP}$ should be compatible
with a solution of $\operatorname{AIP}$. As in [22], this second stage
requires that the $\operatorname{AIP}$ solution should only use those
variables from the $\operatorname{CBLP}$ solution that have nonzero weight.
There are two equivalent ways to enforce this requirement: Either by storing
the nonzero variables at each iteration of $\operatorname{CBLP}$ in the first
stage of the algorithm, or by simply running
$\operatorname{BLP}+\operatorname{AIP}$ as a black box in the second stage of
the algorithm. We adopt the latter option to achieve a simpler presentation.
Concretely, the first stage of $\operatorname{CLAP}$ is performed by
initialising the sets $S_{\mathbf{x},R}$ of constraint-assignment pairs to the
entire relation $R^{\mathbf{A}}$, and then progressively shrinking these sets
by cycling over all constraint-assignment pairs and removing a pair whenever
it yields an infeasible $\operatorname{BLP}$. The second stage, that occurs if
all sets $S_{\mathbf{x},R}$ are nonempty, is performed by cycling over each
feasible constraint-assignment pair and running
$\operatorname{BLP}+\operatorname{AIP}$ on it. As soon as one constraint-
assignment pair is accepted by $\operatorname{BLP}+\operatorname{AIP}$, the
algorithm terminates and outputs Yes. If no constraint-assignment pair is
accepted, the algorithm outputs No.

As in Appendix A, where $\operatorname{BLP}$, $\operatorname{AIP}$, and
$\operatorname{BLP}+\operatorname{AIP}$ are presented in full detail for
completeness, by $\lambda_{\mathbf{x},R}(\mathbf{a})$ we denote the variable
of $\operatorname{BLP}(\mathbf{X},\mathbf{A})$ associated with $\mathbf{x}\in
R^{\mathbf{X}}$ and $\mathbf{a}\in R^{\mathbf{A}}$, where $R\in\sigma$. The
algorithm has polynomial time complexity in the size of the input instance:
Letting $g=\sum_{R\in\sigma}|R^{\mathbf{X}}||R^{\mathbf{A}}|$,
$\mathcal{O}(g^{2})$ $\operatorname{BLP}$ calls and $\mathcal{O}(g)$
$\operatorname{BLP}+\operatorname{AIP}$ calls occur. We say that
$\operatorname{CLAP}$ _accepts_ an instance $\mathbf{X}$ of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if Algorithm 1 returns Yes. We
say that $\operatorname{CLAP}$ _solves_
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if, for every instance
$\mathbf{X}$ of $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, we have (i) if
$\mathbf{X}\to\mathbf{A}$ then $\operatorname{CLAP}$ accepts $\mathbf{X}$, and
(ii) if $\mathbf{X}$ is accepted by $\operatorname{CLAP}$ then
$\mathbf{X}\to\mathbf{B}$.

Input: an instance $\mathbf{X}$ of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ of signature $\sigma$

Output: yes if $\mathbf{X}\to\mathbf{A}$ and no if
$\mathbf{X}\not\to\mathbf{B}$

1 for  _$R\in\sigma$ , $\mathbf{x}\in R^{\mathbf{X}}$_ do

2 set $S_{\mathbf{x},R}:=R^{\mathbf{A}}$;

3

4 end for

5repeat

6 for  _$R\in\sigma,\mathbf{x}\in R^{\mathbf{X}}$ , $\mathbf{a}\in
S_{\mathbf{x},R}$_ do

7 if  _$\operatorname{BLP}(\mathbf{X},\mathbf{A})$ with
$\lambda_{\mathbf{x},R}(\mathbf{a})=1$ and
$\lambda_{\mathbf{x}^{\prime},R^{\prime}}(\mathbf{a}^{\prime})=0$ for every
$R^{\prime}\in\sigma$, $\mathbf{x}^{\prime}\in R^{\prime\mathbf{X}}$, and
$\mathbf{a}^{\prime}\not\in S_{\mathbf{x}^{\prime},R^{\prime}}$ is not
feasible_ then

8 remove $\mathbf{a}$ from $S_{\mathbf{x},R}$;

9 end if

10

11 end for

12

13until  _no set $S_{\mathbf{x},R}$ is changed_;

14if  _some $S_{\mathbf{x},R}$ is empty_ then

15 return No;

16else

17 for  _$R\in\sigma,\mathbf{x}\in R^{\mathbf{X}}$ , $\mathbf{a}\in
S_{\mathbf{x},R}$_ do

18 if  _$\operatorname{BLP}+\operatorname{AIP}(\mathbf{X},\mathbf{A})$ with
$\lambda_{\mathbf{x},R}(\mathbf{a})=1$ and
$\lambda_{\mathbf{x}^{\prime},R^{\prime}}(\mathbf{a}^{\prime})=0$ for every
$R^{\prime}\in\sigma$, $\mathbf{x}^{\prime}\in R^{\prime\mathbf{X}}$, and
$\mathbf{a}^{\prime}\not\in S_{\mathbf{x}^{\prime},R^{\prime}}$ is feasible_
then

19 return Yes;

20 end if

21

22 end for

23 return No;

24 end if

Algorithm 1 The $\operatorname{CLAP}$ algorithm

#### Characterisation

Our first main result – Theorem 13 – is a minion-theoretic characterisation of
the power of the $\operatorname{CLAP}$ algorithm. In particular, we will
introduce in Definition 12 a minion $\mathscr{C}$ such that, for any
$\operatorname{PCSP}$ template $(\mathbf{A},\mathbf{B})$, the
$\operatorname{CLAP}$ algorithm solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if and only if there is a minion
homomorphism from $\mathscr{C}$ to
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$. The two directions will be proved
in Theorems 30 and 31, respectively, in Section 4. Combining Theorem 30 with
our second main result – Theorem 15, proved in Section 5 – will then yield a
sufficient condition for $\operatorname{CLAP}$ to solve a given
$\operatorname{PCSP}$ template, in terms of a weak notion of symmetry for the
polymorphisms of the template.

The $L$-ary objects of the minion $\mathscr{C}$ are pairs $(M,\bm{\mu})$,
where $M$ is a matrix with $L$ rows and infinitely many columns encoding the
$\operatorname{BLP}$ computations of $\operatorname{CLAP}$ and $\bm{\mu}$ is
an $L$-ary vector of integers encoding the $\operatorname{AIP}$ computation of
$\operatorname{CLAP}$. The matrices $M$ in $\mathscr{C}$ have a special
structure, which we call ‘skeletal’.

######  Definition 11.

Let $M$ be a $p\times\aleph_{0}$ matrix with $p\in\mathbb{N}$. We say that $M$
is _skeletal_ if, for each $j\in[p]$, either
$\mathbf{e}_{j}^{T}M=\mathbf{0}^{T}_{\aleph_{0}}$ or
$M\mathbf{e}_{i}=\mathbf{e}_{j}$ for some $i\in\mathbb{N}$.

In other words, either the $j$-th row of $M$ is the zero vector or some column
of $M$ is the $j$-th standard unit vector. Equivalently, $M$ is skeletal if
there exist permutation matrices $P\in\mathbb{R}^{p,p}$ and
$Q\in\mathbb{R}^{\aleph_{0},\aleph_{0}}$ such that $\displaystyle
PMQ=\begin{bmatrix}I_{k}&\tilde{M}\\\ O&O\end{bmatrix}$ for some $k\leq p$ and
some $\tilde{M}\in\mathbb{R}^{k,\aleph_{0}}$. The name indicates that the
‘body’ of a skeletal matrix (the nonzero rows) is completely supported by a
‘skeleton’ (the identity block).

We are now ready to define the minion $\mathscr{C}$. The $L$-ary objects of
$\mathscr{C}$ are pairs $(M,\bm{\mu})$, where $M$ is a skeletal matrix of size
$L\times\aleph_{0}$ and $\bm{\mu}$ is an affine vector (i.e., an integer
vector whose entries sum up to one) of size $L$. We require that every column
of $M$ should be stochastic and $M$ should have only finitely many different
columns; the latter is formalised in $(c_{5})$ in Definition 12, which says
that starting from some point all the columns are equal. We also require a
particular relationship between $M$ and $\bm{\mu}$ formalised in $(c_{4})$.

######  Definition 12.

For $L\in\mathbb{N}$, let $\mathscr{C}^{(L)}$ be the set of pairs
$(M,\bm{\mu})$ such that $M\in\mathbb{Q}^{L,\aleph_{0}}$,
$\bm{\mu}\in\mathbb{Z}^{L}$, and the following requirements are met:

$\displaystyle\begin{array}[]{ll}(c_{1})\quad M\mbox{ is entrywise
nonnegative};&(c_{4})\quad\operatorname{supp}(\bm{\mu})\subseteq\operatorname{supp}(M\mathbf{e}_{1});\\\
(c_{2})\quad\mathbf{1}_{L}^{T}M=\mathbf{1}_{\aleph_{0}}^{T};&(c_{5})\quad\exists
t\in\mathbb{N}\mbox{ such that }M\mathbf{e}_{i}=M\mathbf{e}_{t}\hskip
11.38092pt\forall i\geq t;\\\
(c_{3})\quad\mathbf{1}_{L}^{T}\bm{\mu}=1;&(c_{6})\quad M\mbox{ is skeletal.
}\end{array}$

We define $\mathscr{C}$ as the disjoint union of $L$-ary parts,
$\mathscr{C}\coloneqq\bigcup_{L\geq 1}\mathscr{C}^{(L)}$.

We defined $\mathscr{C}$ as a set. For $\mathscr{C}$ to be a minion, we need
to define the minor operation on $\mathscr{C}$ and verify that it preserves
the structure of $\mathscr{C}$. This is easy and done in Section 4.1.

Our first result is the following characterisation of the power of
$\operatorname{CLAP}$.

######  Theorem 13.

Let $(\mathbf{A},\mathbf{B})$ be a PCSP template. Then, $\operatorname{CLAP}$
solves $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if and only if there is a
minion homomorphism from $\mathscr{C}$ to
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$.

#### H-symmetry

Our second main result is a sufficient condition on a PCSP template
$(\mathbf{A},\mathbf{B})$ to guarantee that $\operatorname{CLAP}$ solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$. The condition is through
symmetries satisfied by polymorphisms of the template. In particular, in
Theorem 15 we will show that if $\operatorname{Pol}(\mathbf{A},\mathbf{B})$
contains infinitely many operations that are ‘$H$-symmetric’ for a suitable
matrix $H$, then there is a minion homomorphism from $\mathscr{C}$ to
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$, and thus $\operatorname{CLAP}$
solves $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ by Theorem 30.

In order to define the notion of $H$-symmetry, we need a few auxiliary
definitions. A vector $\mathbf{w}=(w_{i})\in\mathbb{R}^{p}$ is _tieless_ if,
for any two indices $i\neq i^{\prime}\in[p]$, $w_{i}\neq 0$ $\Rightarrow$
$w_{i}\neq w_{i^{\prime}}$. A _tie matrix_ is a matrix having integer
nonnegative entries, each of whose columns is a tieless vector. Given an
$m\times p$ tie matrix $H$, we say that a vector $\mathbf{v}\in\mathbb{R}^{p}$
is _$H$ -tieless_ if $H\mathbf{v}$ is tieless.

Let $A$ be a finite set, let $L\in\mathbb{N}$, and take
$\mathbf{a}=(a_{1},\dots,a_{L})\in A^{L}$. We define the (multiplicity) vector
$\mathbf{a}^{\\#}$ as the integer vector of size $|A|$ whose $a$-th entry is
$|\\{i\in[L]:a_{i}=a\\}|$ for each $a\in A$.

######  Definition 14.

Let $A,B$ be finite sets, and consider a function $f:A^{L}\rightarrow B$ for
some $L\in\mathbb{N}$. Given an $m\times|A|$ tie matrix $H$, we say that $f$
is _$H$ -symmetric_ if

$\displaystyle f_{/\pi}(\mathbf{a})=f(\mathbf{a})$
$\displaystyle\forall\pi:[L]\rightarrow[L]\mbox{ permutation},\hskip
8.5359pt\forall\mathbf{a}\in A^{L}\mbox{ such that }\mathbf{a}^{\\#}\mbox{ is
$H$-tieless}.$

Our second result is the following sufficient condition for tractability of
PCSPs.

######  Theorem 15.

Let $(\mathbf{A},\mathbf{B})$ be a PCSP template and suppose
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ contains $H$-symmetric operations
of arbitrarily large arity for some $m\times|A|$ tie matrix $H$,
$m\in\mathbb{N}$. Then there exists a minion homomorphism from $\mathscr{C}$
to $\operatorname{Pol}(\mathbf{A},\mathbf{B})$.

Recall from Definition 11 the notion of a skeletal matrix. As it will be clear
from the rest of the paper, the ‘skeleton’ represents the link between
$\operatorname{CLAP}$ and the above-defined notion of $H$-symmetry. Indeed, on
the one hand the presence of the identity block in a skeletal matrix captures
the fact that each $\operatorname{BLP}$ solution computed by
$\operatorname{CLAP}$ gives probability $1$ to some constraint-assignment pair
and probability $0$ to all other constraint-assignment pairs for the same
constraint (cf. line 6 of Algorithm 1). On the other hand, Lemma 35 (stated
and proved in Section 5) shows that finitely many skeletal matrices can always
be simultaneously reduced to $H$-tieless probability distributions – which are
exactly the distributions on which $H$-symmetric functions are symmetric (cf.
Definition 14).

We now mention some consequences of Theorem 15. First, observe that a vector
of size $1$ is always tieless. Hence, if we take any $1\times|A|$ integer
nonnegative matrix as $H$, we have that $H$ is a tie matrix and
$\mathbf{a}^{\\#}$ is $H$-tieless for each tuple $\mathbf{a}$ in the domain of
$f$; therefore, for such an $H$, $f$ being $H$-symmetric reduces to $f$ being
symmetric. On the other hand, having Definition 14 in mind, adding rows to $H$
increases the chance that $H\mathbf{a}^{\\#}$ has some ties, in which case $f$
is released from the requirement of being symmetric on $\mathbf{a}$. In this
sense, $H$ encodes the ‘exceptions to symmetry’ that $f$ is allowed to have:
The more rows $H$ has, the stronger Theorem 15 becomes. If, for instance, $H$
is the identity matrix of order $|A|$, then an $H$-symmetric operation needs
to be symmetric only on those tuples where each entry occurs with a different
multiplicity. A very special example of such an $I_{|A|}$-symmetric operation
is a function $f$ that returns (the homomorphic image of) the _most-frequent_
entry in the input tuple whenever it is unique, and, in any other case, $f$
is, say, (the homomorphic image of) a projection. Other, more creative choices
for $H$ allow capturing operations having more complex exceptions to symmetry,
as shown in Example 16.

Theorems 13 and 15 together establish that the $\operatorname{CLAP}$ algorithm
solves any PCSP template admitting arbitrarily large polymorphisms having some
exceptions to symmetry that can be encoded via a tie matrix.

The importance of the next example lies in the fact that it provably separates
$\operatorname{CLAP}$ from finite tractability and
$\operatorname{BLP}+\operatorname{AIP}$; i.e., there are PCSP templates
solvable by $\operatorname{CLAP}$ that are not finitely tractable and not
solvable by $\operatorname{BLP}+\operatorname{AIP}$.

######  Example 16.

Recall the PCSP template $(\mathbf{A},\mathbf{B})$ from Example 10, where it
was shown that $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is not finitely
tractable and not solved by the $\operatorname{BLP}+\operatorname{AIP}$
algorithm from [22]. We will show that
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ is solved by
$\operatorname{CLAP}$.

Take $L\in\mathbb{N}$ and consider the function $f:A^{L}\rightarrow B$ defined
as follows: For $\mathbf{a}=(a_{1},\dots,a_{L})\in A^{L}$,

  * •

if $\mathbf{a}\in\\{0,1\\}^{L}$, look at $\mathbf{a}^{\\#}_{1}$, i.e., the
multiplicity of $1\in A$ in the tuple $\mathbf{a}$;

    * $\ast$

if $\mathbf{a}^{\\#}_{1}<\frac{L}{3}$, set $f(\mathbf{a})=0$;

    * $\ast$

if $\mathbf{a}^{\\#}_{1}>\frac{L}{3}$, set $f(\mathbf{a})=1$;

    * $\ast$

if $\mathbf{a}^{\\#}_{1}=\frac{L}{3}$, set $f(\mathbf{a})=a_{1}$;

  * •

if $\mathbf{a}\in\\{2,3,4,5,6\\}^{L}$,

    * $\ast$

if there is a unique element $a\in A$ having maximum multiplicity in
$\mathbf{a}$, set $f(\mathbf{a})=a$;

    * $\ast$

if there is more than one element of $A$ having maximum multiplicity in
$\mathbf{a}$, set $f(\mathbf{a})=a_{1}$;

  * •

otherwise, set $f(\mathbf{a})=0$.777Assigning any value in $\\{0,\ldots,6\\}$
to $f(\mathbf{a})$ would work here.

We claim that $f\in\operatorname{Pol}(\mathbf{A},\mathbf{B})$. To see that $f$
preserves $R_{1}$, consider a tuple
$\bm{\rho}=(\mathbf{r}_{1},\dots,\mathbf{r}_{L})$ of elements of
$R_{1}^{\mathbf{A}}$, where $\mathbf{r}_{i}=(a_{i},b_{i},c_{i})$ for
$i\in[L]$. We shall let $\mathbf{a}=(a_{1},\dots,a_{L})$,
$\mathbf{b}=(b_{1},\dots,b_{L})$, and $\mathbf{c}=(c_{1},\dots,c_{L})$. Notice
that

$\displaystyle\mathbf{a}^{\\#}_{1}+\mathbf{b}^{\\#}_{1}+\mathbf{c}^{\\#}_{1}=L.$
(3)

If $f(\mathbf{a})=f(\mathbf{b})=f(\mathbf{c})=0$, then
$\mathbf{a}^{\\#}_{1}\leq\frac{L}{3}$, $\mathbf{b}^{\\#}_{1}\leq\frac{L}{3}$,
and $\mathbf{c}^{\\#}_{1}\leq\frac{L}{3}$; by (3), this implies that
$\mathbf{a}^{\\#}_{1}=\mathbf{b}^{\\#}_{1}=\mathbf{c}^{\\#}_{1}=\frac{L}{3}$.
Hence,
$(0,0,0)=(f(\mathbf{a}),f(\mathbf{b}),f(\mathbf{c}))=(a_{1},b_{1},c_{1})=\mathbf{r}_{1}\in
R_{1}^{\mathbf{A}}$, a contradiction. Similarly,
$f(\mathbf{a})=f(\mathbf{b})=f(\mathbf{c})=1$ would yield
$\mathbf{a}^{\\#}_{1}\geq\frac{L}{3}$, $\mathbf{b}^{\\#}_{1}\geq\frac{L}{3}$,
and $\mathbf{c}^{\\#}_{1}\geq\frac{L}{3}$; again by (3), this implies that
$\mathbf{a}^{\\#}_{1}=\mathbf{b}^{\\#}_{1}=\mathbf{c}^{\\#}_{1}=\frac{L}{3}$,
hence
$(1,1,1)=(f(\mathbf{a}),f(\mathbf{b}),f(\mathbf{c}))=(a_{1},b_{1},c_{1})=\mathbf{r}_{1}\in
R_{1}^{\mathbf{A}}$, also a contradiction. We conclude that
$f(\bm{\rho})=(f(\mathbf{a}),f(\mathbf{b}),f(\mathbf{c}))\in
R_{1}^{\mathbf{B}}$, thus showing that $f$ preserves $R_{1}$.

As for $R_{2}$, let $\bm{\rho}=(\mathbf{r}_{1},\dots,\mathbf{r}_{L})$ be a
tuple of elements of $R_{2}^{\mathbf{A}}$, where
$\mathbf{r}_{i}=(a_{i},b_{i})$ for $i\in[L]$, and let
$\mathbf{a}=(a_{1},\dots,a_{L})$ and $\mathbf{b}=(b_{1},\dots,b_{L})$. The
directed graph having vertex set $\\{2,3,4,5,6\\}$ and edge set
$R_{2}^{\mathbf{A}}=R_{2}^{\mathbf{B}}$ consists of the disjoint union of a
directed $2$-cycle and a directed $3$-cycle and, hence, all of its vertices
have in-degree and out-degree one. As a consequence, the multiplicity of a
directed edge $(a,b)$ in the tuple $\bm{\rho}$ equals both the multiplicity of
$a$ in $\mathbf{a}$ and the multiplicity of $b$ in $\mathbf{b}$. Therefore, if
the tuple $\bm{\rho}$ has a unique element $\mathbf{r}=(a,b)$ with maximum
multiplicity, then
$f(\bm{\rho})=(f(\mathbf{a}),f(\mathbf{b}))=(a,b)=\mathbf{r}\in
R_{2}^{\mathbf{B}}$. Otherwise, $f(\bm{\rho})=(a_{1},b_{1})=\mathbf{r}_{1}\in
R_{2}^{\mathbf{B}}$. This shows that $f$ preserves $R_{2}$, too, and is thus a
polymorphism of $(\mathbf{A},\mathbf{B})$.

Consider the matrix $H=\operatorname{diag}(1,2,1,1,1,1,1)$, and observe that
$H$ is a tie matrix. We claim that $f$ is $H$-symmetric. Let
$\pi:[L]\rightarrow[L]$ be a permutation, and take a tuple
$\mathbf{a}=(a_{1},\dots,a_{L})\in A^{L}$ such that $\mathbf{a}^{\\#}$ is
$H$-tieless; i.e., the vector
$H\mathbf{a}^{\\#}=(\mathbf{a}^{\\#}_{0},2\mathbf{a}^{\\#}_{1},\mathbf{a}^{\\#}_{2},\mathbf{a}^{\\#}_{3},\mathbf{a}^{\\#}_{4},\mathbf{a}^{\\#}_{5},\mathbf{a}^{\\#}_{6})$
is tieless. Write $\tilde{\mathbf{a}}=(a_{\pi(1)},\dots,a_{\pi(L)})$, and
observe that $\tilde{\mathbf{a}}^{\\#}=\mathbf{a}^{\\#}$.

  * •

If $\mathbf{a}\in\\{0,1\\}^{L}$, we get $\mathbf{a}^{\\#}_{0}\neq
2\mathbf{a}^{\\#}_{1}$; since $\mathbf{a}^{\\#}_{0}+\mathbf{a}^{\\#}_{1}=L$,
this gives $2\mathbf{a}^{\\#}_{1}\neq L-\mathbf{a}^{\\#}_{1}$ so that
$\mathbf{a}^{\\#}_{1}\neq\frac{L}{3}$. As a consequence,
$f(\mathbf{a})=f(\tilde{\mathbf{a}})$.

  * •

If $\mathbf{a}\in\\{2,3,4,5,6\\}^{L}$, the condition above implies that the
tuple
$(\mathbf{a}^{\\#}_{2},\mathbf{a}^{\\#}_{3},\mathbf{a}^{\\#}_{4},\mathbf{a}^{\\#}_{5},\mathbf{a}^{\\#}_{6})$
has a unique maximum element and, hence, there is a unique element $a$ of $A$
having maximum multiplicity in $\mathbf{a}$ (and in $\tilde{\mathbf{a}}$).
Therefore, $f(\mathbf{a})=a=f(\tilde{\mathbf{a}})$.

  * •

If $\mathbf{a}\not\in\\{0,1\\}^{L}\cup\\{2,3,4,5,6\\}^{L}$, then
$f(\mathbf{a})=0=f(\tilde{\mathbf{a}})$.

We conclude that, in each case,
$f(\mathbf{a})=f(\tilde{\mathbf{a}})=f_{/\pi}(\mathbf{a})$, which means that
$f$ is $H$-symmetric. By Theorems 13 and 15, $\operatorname{CLAP}$ solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$.

######  Remark 17.

Consider the minion
$\mathscr{M}_{\operatorname{\operatorname{BLP}+\operatorname{AIP}}}$ from [22]
(cf. Appendix A.3). A direct consequence of Example 16, Theorem 13, and [22,
Lemma 5.4] is that there is no minion homomorphism from
$\mathscr{M}_{\operatorname{\operatorname{BLP}+\operatorname{AIP}}}$ to
$\mathscr{C}$. On the other hand, the function

$\displaystyle\vartheta:\mathscr{C}$
$\displaystyle\rightarrow\mathscr{M}_{\operatorname{\operatorname{BLP}+\operatorname{AIP}}}$
$\displaystyle(M,\bm{\mu})$ $\displaystyle\mapsto(M\mathbf{e}_{1},\bm{\mu})$

is readily seen to be a minion homomorphism. It follows that
$\operatorname{CLAP}$ solves any PCSP template solved by
$\operatorname{BLP}+\operatorname{AIP}$ (as is also clear from the description
of the two algorithms).

######  Remark 18.

Similar to [22], the assumption in Theorem 15 can be weakened as follows:
Instead of requiring $H$-symmetric polymorphisms of arbitrarily large arity,
it turns out to be enough requiring $H$-block-symmetric polymorphisms of
arbitrarily large width, where the definition of an $H$-block-symmetric
operation mirrors that of a block-symmetric operation in [22]. The proof of
this possibly stronger result is very similar to that of Theorem 15. For
completeness, we include it in Appendix C. We point out that we do not know
whether the condition in Theorem 15 (or the possibly weaker condition based on
$H$-block-symmetric polymorphisms) is necessary for tractability via CLAP, but
we suspect it is not.

######  Remark 19.

A possibly stronger version of the $\operatorname{CLAP}$ algorithm consists in
running $\operatorname{BLP}+\operatorname{AIP}$ (instead of just
$\operatorname{BLP}$) at each iteration in the for loop in lines $5$–$9$ of
Algorithm 1, and then removing the additional for loop in lines $14$–$18$.
This algorithm can be called C($\operatorname{BLP}+\operatorname{AIP}$). An
analysis entirely analogous to the one presented in this paper shows that the
power of C($\operatorname{BLP}+\operatorname{AIP}$) is captured by the minion
$\tilde{\mathscr{C}}$ defined like $\mathscr{C}$ with the following
difference: The $L$-ary elements of $\tilde{\mathscr{C}}$ are pairs $(M,N)$,
where $M$ is as in $\mathscr{C}$ while $N$ is an integer matrix of the same
size as $M$ taking the role of $\bm{\mu}$ (in particular, $N$ satisfies the
‘refinement condition’
$\operatorname{supp}(N\mathbf{e}_{i})\subseteq\operatorname{supp}(M\mathbf{e}_{i})$
$\forall i\in\mathbb{N}$, analogous to $(c_{4})$ in Definition 12). A possible
direction for future research is to investigate whether the richer structure
of $\tilde{\mathscr{C}}$ can be exploited to obtain a stronger version of
Theorem 15.

######  Remark 20.

For CSPs, the characterisation of bounded width [9, 25] and its collapse [6]
was preceded by a characterisation of width-1 CSPs [41, 37] and the collapse
of width 2 to width 1 [34]. Thus the difference between width-1 CSPs and
bounded-width CSPs is well understood. BLP and SBLP are the (convex
relaxation) analogues of width 1 and SAC, respectively, and SAC solves all
bounded-width CSPs [56]. Therefore, a natural question is whether a similar
analysis can cast light on the difference in power between BLP on one side,
and SBLP (and thus perhaps also of CBLP and CLAP) on the other side. We remark
on two obstacles: Firstly, BLP is strictly more powerful than width 1 for CSPs
[60]. Secondly, a good characterisation of the power of SBLP (and stronger
algorithms studied in the present paper) would imply that these algorithms
solve, in the special case of CSPs, all bounded-width CSPs – a non-trivial
result implied by [56].

##  4 The power of the CLAP algorithm

The goal of this section is to prove Theorem 13. In Section 4.1, we will
verify that $\mathscr{C}$, which appears in the statement of Theorem 13, is
indeed a minion. In Sections 4.2 and 4.3, we will establish a compactness
argument and present a condition that captures $\operatorname{CLAP}$,
respectively; both will be needed in the proof of Theorem 13. The two
directions of Theorem 13 will be then proved in Section 4.4.

Minions are not only useful for capturing the complexity of PCSPs but also for
characterising the power of algorithms. This will be done by using the concept
of the free structure generated, for a given minion, by a relational structure
[22] (cf. [8, Definition 4.1] for the definition in the special case of
minions of functions).

######  Definition 21.

Let $\mathscr{M}$ be a minion and let $\mathbf{A}$ be a (finite) relational
structure with signature $\sigma$. The _free structure_
$\mathbb{F}_{\mathscr{M}}(\mathbf{A})$ is a relational structure with domain
$\mathscr{M}^{(|A|)}$ (potentially infinite) and signature $\sigma$. Given a
relation $R\in\sigma$ of arity $k$, a tuple $(M_{1},\dots,M_{k})$ of elements
of $\mathscr{M}^{(|A|)}$ belongs to $R^{\mathbb{F}_{\mathscr{M}}(\mathbf{A})}$
if and only if there is some $Q\in\mathscr{M}^{(|R^{\mathbf{A}}|)}$ such that
$M_{i}=Q_{/\pi_{i}}$ for each $i\in[k]$, where $\pi_{i}:R^{\mathbf{A}}\to A$
maps $\textbf{a}\in R^{\mathbf{A}}$ to its $i$-th coordinate $a_{i}$.

The next result will be useful to establish the connection between our
algorithm $\operatorname{CLAP}$, presented in Section 3, and the minion
$\mathscr{C}$.

######  Lemma 22.

Let $\mathscr{M}$ be a minion and let $(\mathbf{A},\mathbf{B})$ be a PCSP
template. Then there is a minion homomorphism from $\mathscr{M}$ to
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ if and only if
$\mathbb{F}_{\mathscr{M}}(\mathbf{A})\to\mathbf{B}$.

The proof of Lemma 22 is based on that of [8, Lemma 4.4], which proves one-to-
one correspondence but only for minions of functions. For completeness, we
prove Lemma 22 in Appendix B.

###  4.1 $\mathscr{C}$ is a minion

The minor operation on $\mathscr{C}$ is naturally defined via a matrix
multiplication with a matrix that encodes the minor map. For a function
$\pi:[L]\rightarrow[L^{\prime}]$, let ${P_{\pi}}$ be the $L^{\prime}\times L$
matrix whose $(i,j)$-th entry is $1$ if $\pi(j)=i$, and $0$ otherwise. Note
that ${P_{\pi}^{T}}\mathbf{1}_{L^{\prime}}=\mathbf{1}_{L}$ and, for each
$i\in[L^{\prime}]$,
${P_{\pi}^{T}}\mathbf{e}_{i}=\sum_{j\in\pi^{-1}(i)}\mathbf{e}_{j}$.

######  Definition 23.

For $(M,\bm{\mu})\in\mathscr{C}^{(L)}$, we define $M_{/\pi}={P_{\pi}}M$ and
$\bm{\mu}_{/\pi}={P_{\pi}}\bm{\mu}$, and we let the minor of $(M,\bm{\mu})$
with respect to $\pi$ be
$(M,\bm{\mu})_{/\pi}\coloneqq(M_{/\pi},\bm{\mu}_{/\pi})$.

We remark that this definition is consistent with the minions
$\mathscr{Q}_{\operatorname{conv}}$ and $\mathscr{Z}_{\operatorname{aff}}$
studied in [8], and the minion
$\mathscr{M}_{\operatorname{\operatorname{BLP}+\operatorname{AIP}}}$ studied
in [22], cf. Appendices A.1, A.2, and A.3.

######  Proposition 24.

$\mathscr{C}$ is a minion.

###### Proof.

Write $M=[m_{ij}]$ and $\bm{\mu}=(\mu_{i})$. Observe that
$M_{/\pi}\in\mathbb{Q}^{L^{\prime},\aleph_{0}}$ and
$\bm{\mu}_{/\pi}\in\mathbb{Z}^{L^{\prime}}$. The requirements
$(c_{1}),(c_{2}),(c_{3})$, and $(c_{5})$ are trivially satisfied by
$(M,\bm{\mu})_{/\pi}$. As for $(c_{4})$, suppose that
$\mathbf{e}_{i}^{T}{P_{\pi}}M\mathbf{e}_{1}=0$ but
$\mathbf{e}_{i}^{T}{P_{\pi}}\bm{\mu}\neq 0$. It follows that $\mu_{j}\neq 0$
for some $j\in\pi^{-1}(i)$. Hence, $m_{j1}>0$ and, then,

$\displaystyle\mathbf{e}_{i}^{T}{P_{\pi}}M\mathbf{e}_{1}=\sum_{j^{\prime}\in\pi^{-1}(i)}\mathbf{e}_{j^{\prime}}^{T}M\mathbf{e}_{1}\geq\mathbf{e}_{j}^{T}M\mathbf{e}_{1}>0,$

which is a contradiction. We now show that $M_{/\pi}$ is skeletal. Choose
$j\in[L^{\prime}]$, and suppose that
$\mathbf{e}_{j}^{T}M_{/\pi}\neq\mathbf{0}_{\aleph_{0}}^{T}$. We obtain

$\displaystyle\mathbf{0}_{\aleph_{0}}\neq
M^{T}{P_{\pi}^{T}}\mathbf{e}_{j}=\sum_{{\ell}\in\pi^{-1}(j)}M^{T}\mathbf{e}_{\ell}$

and, in particular, $\exists{\ell}\in\pi^{-1}(j)$ such that
$\mathbf{e}_{\ell}^{T}M\neq\mathbf{0}_{\aleph_{0}}^{T}$. Since $M$ is
skeletal, this implies that $M\mathbf{e}_{i}=\mathbf{e}_{\ell}$ for some
$i\in\mathbb{N}$. This yields

$\displaystyle
M_{/\pi}\mathbf{e}_{i}={P_{\pi}}M\mathbf{e}_{i}={P_{\pi}}\mathbf{e}_{\ell}=\mathbf{e}_{\pi({\ell})}=\mathbf{e}_{j}$

as required. Hence, $(c_{6})$ is satisfied, too, and
$(M,\bm{\mu})_{/\pi}\in\mathscr{C}^{(L^{\prime})}$.

Finally, considering $\tilde{\pi}:[L^{\prime}]\to[L^{\prime\prime}]$ and the
identity map $\operatorname{id}:[L]\to[L]$, one readily checks that
${P_{\tilde{\pi}\circ\pi}}={P_{\tilde{\pi}}}{P_{\pi}}$ and
${P_{\operatorname{id}}}=I_{L}$. Hence, the minor operations defined above
satisfy the requirements of Definition 6. ∎

###  4.2 A compactness argument for $\mathscr{C}$

The set $\mathscr{C}^{(L)}$ of the $L$-ary objects in $\mathscr{C}$ is
infinite unless $L=1$. As a consequence, given a relational structure
$\mathbf{A}$ whose domain has size at least $2$, the free structure
$\mathbb{F}_{\mathscr{C}}(\mathbf{A})$ has an infinite domain. We now describe
a standard compactness argument analogous to [8, Remark 7.13] that will
circumvent this inconvenience.

For $D,L\in\mathbb{N}$, consider the set

$\displaystyle\mathscr{C}_{D}^{(L)}=\\{(M,\bm{\mu})\in\mathscr{C}^{(L)}:DM\mbox{
is entrywise integer, }M\mathbf{e}_{i}=M\mathbf{e}_{D}\hskip 5.69046pt\forall
i\geq D,\mbox{ and }\mathbf{1}_{L}^{T}|\bm{\mu}|\leq D\\},$

where $|\bm{\mu}|$ denotes the vector whose entries are the absolute values of
the entries of $\bm{\mu}$. Since $\mathscr{C}_{D}^{(L)}$ is unambiguously
determined by $L\times(D+1)$ integer numbers belonging to the set
$\\{-D,\dots,D\\}$, it is finite. Observe that the set
$\mathscr{C}_{D}=\bigcup_{L\in\mathbb{N}}\mathscr{C}_{D}^{(L)}$ is closed
under taking minors. Indeed, given $(M,\bm{\mu})\in\mathscr{C}_{D}^{(L)}$ and
$\pi:[L]\rightarrow[L^{\prime}]$, $D{P_{\pi}}M={P_{\pi}}DM$ is entrywise
integer, ${P_{\pi}}M\mathbf{e}_{i}={P_{\pi}}M\mathbf{e}_{D}$ $\forall i\geq
D$, and
$\mathbf{1}_{L^{\prime}}^{T}|{P_{\pi}}\bm{\mu}|\leq\mathbf{1}_{L^{\prime}}^{T}{P_{\pi}}|\bm{\mu}|=\mathbf{1}_{L}^{T}|\bm{\mu}|\leq
D$. Hence, $\mathscr{C}_{D}$ is a sub-minion of $\mathscr{C}$. Observe also
that $\mathscr{C}=\bigcup_{D\in\mathbb{N}}\mathscr{C}_{D}$. To see this, take
$(M,\bm{\mu})\in\mathscr{C}^{(L)}$ and suppose that
$M\mathbf{e}_{i}=M\mathbf{e}_{t}$ $\forall i\geq t$. Let $\tilde{D}$ be a
common denominator of the finite set of rational numbers
$\\{m_{ij}:i\in[L],j\in[t]\\}$, so that $\tilde{D}M$ is entrywise integer. Let
also $\hat{D}=\mathbf{1}_{L}^{T}|\bm{\mu}|$. Then,
$(M,\bm{\mu})\in\mathscr{C}_{t\tilde{D}\hat{D}}$.

######  Proposition 25.

Let $\mathscr{M}$ be a minion such that $\mathscr{M}^{(L)}$ is finite for each
$L\in\mathbb{N}$, and suppose that there exist minion homomorphisms
$\xi_{D}:\mathscr{C}_{D}\rightarrow\mathscr{M}$ for each $D\in\mathbb{N}$.
Then there exists a minion homomorphism
$\zeta:\mathscr{C}\rightarrow\mathscr{M}$.

###### Proof.

For $D\in\mathbb{N}$, let $\mathscr{C}_{\\{D\\}}=\bigcup_{L\leq
D}\mathscr{C}_{D!}^{(L)}$. Observe that $\mathscr{C}_{\\{D\\}}$ is a finite
set and $\mathscr{C}_{\\{D\\}}\subseteq\mathscr{C}_{\\{D+1\\}}$. Moreover,
$\bigcup_{D\in\mathbb{N}}\mathscr{C}_{\\{D\\}}=\bigcup_{D\in\mathbb{N}}\mathscr{C}_{D}=\mathscr{C}$.
Indeed, given $D^{\prime}\in\mathbb{N}$, we have that
$\mathscr{C}_{\\{D^{\prime}\\}}\subseteq\mathscr{C}_{D^{\prime}!}\subseteq\bigcup_{D\in\mathbb{N}}\mathscr{C}_{D}$,
and, given $L\in\mathbb{N}$,
$\mathscr{C}_{D^{\prime}}^{(L)}\subseteq\mathscr{C}_{(D^{\prime}L)!}^{(L)}\subseteq\mathscr{C}_{\\{D^{\prime}L\\}}\subseteq\bigcup_{D\in\mathbb{N}}\mathscr{C}_{\\{D\\}}$.
Consider an infinite rooted tree whose vertices are all the restrictions of
the homomorphisms $\xi_{D}$ to some $\mathscr{C}_{\\{D^{\prime}\\}}$, whose
root is the empty mapping, and the parent of a vertex corresponding to a
function $\mathscr{C}_{\\{D^{\prime}+1\\}}\rightarrow\mathscr{M}$ is the
vertex corresponding to the restriction of the function to
$\mathscr{C}_{\\{D^{\prime}\\}}$. This is an infinite connected tree.
Moreover, since $\mathscr{M}^{(L)}$ is finite for each $L\in\mathbb{N}$ and
since minion homomorphisms preserve the arities, there exist only finitely
many distinct restrictions of minion homomorphisms to $\mathscr{C}_{\\{D\\}}$;
hence, the tree is locally finite. By Kőnig’s Lemma, it contains an infinite
path, which corresponds to an infinite chain of maps
$\zeta_{i}:\mathscr{C}_{\\{i\\}}\rightarrow\mathscr{M}$ such that
$\zeta_{i+1}$ extends $\zeta_{i}$ $\forall i\in\mathbb{N}$. Their union
$\zeta:\mathscr{C}\rightarrow\mathscr{M}$ is then a minion homomorphism. ∎

###  4.3 The CLAP condition

Given a finite set $C$, consider the set $\mathbb{S}(C)$ of the rational
stochastic vectors of size $|C|$. Let ${U}\subseteq C^{k}$. For $i\in[k]$,
consider the $|C|\times|U|$ matrix ${E}^{({U},i)}$ such that, for $c\in C$ and
$\mathbf{c}=(c_{1},\dots,c_{k})\in{U}$, the $(c,\mathbf{c})$-th entry of
${E}^{({U},i)}$ is $1$ if $c_{i}=c$, and $0$ otherwise. Given
$\bm{\xi}\in\mathbb{S}({U})$ and $i\in[k]$, we define the $i$-th _marginal_ of
$\bm{\xi}$ as

$\displaystyle\bm{\xi}^{(i)}={{E}^{({U},i)}}\bm{\xi}.$

Observe that

$\displaystyle{\bm{\xi}^{(i)}}^{T}\mathbf{1}_{|C|}=\bm{\xi}^{T}{{E}^{({U},i)}}^{T}\mathbf{1}_{|C|}=\bm{\xi}^{T}\mathbf{1}_{|{U}|}=1,$

so that $\bm{\xi}^{(i)}\in\mathbb{S}(C)$. We also define the set
$\mathbb{Z}(C)$ of the integer vectors of size $|C|$ whose entries sum up to
$1$. Given ${U}\subseteq C^{k}$, $\bm{\zeta}\in\mathbb{Z}({U})$, and
$i\in[k]$, we define

$\displaystyle\bm{\zeta}^{(i)}={{E}^{({U},i)}}\bm{\zeta}.$

As before, observe that

$\displaystyle{\bm{\zeta}^{(i)}}^{T}\mathbf{1}_{|C|}=\bm{\zeta}^{T}{{E}^{({U},i)}}^{T}\mathbf{1}_{|C|}=\bm{\zeta}^{T}\mathbf{1}_{|{U}|}=1,$

so $\bm{\zeta}^{(i)}\in\mathbb{Z}(C)$.

Let $\mathbf{A}$ be a relational structure having domain $A$ and signature
$\sigma$. We define the relational structures $\mathbb{S}(\mathbf{A})$ and
$\mathbb{Z}(\mathbf{A})$ as follows:

  * •

$\mathbb{S}(\mathbf{A})$ has domain $\mathbb{S}(A)$ and, for every symbol
$R\in\sigma$ of arity $k$,
$R^{\mathbb{S}(\mathbf{A})}=\\{(\bm{\xi}^{(1)},\dots,\bm{\xi}^{(k)}):\bm{\xi}\in\mathbb{S}(R^{\mathbf{A}})\\}$;

  * •

$\mathbb{Z}(\mathbf{A})$ has domain $\mathbb{Z}(A)$ and, for every symbol
$R\in\sigma$ of arity $k$,
$R^{\mathbb{Z}(\mathbf{A})}=\\{(\bm{\zeta}^{(1)},\dots,\bm{\zeta}^{(k)}):\bm{\zeta}\in\mathbb{Z}(R^{\mathbf{A}})\\}$.

######  Remark 26.

$\mathbb{S}(\mathbf{A})$ and $\mathbb{Z}(\mathbf{A})$ are denoted by
$\operatorname{LP}(\mathbf{A})$ and $\operatorname{IP}(\mathbf{A})$ in [8],
respectively. As noted in [8, Remarks 7.11 and 7.21], $\mathbb{S}(\mathbf{A})$
coincides with the free structure of the minion
$\mathscr{Q}_{\operatorname{conv}}$ generated by $\mathbf{A}$ and, similarly,
$\mathbb{Z}(\mathbf{A})$ is the free structure of the minion
$\mathscr{Z}_{\operatorname{aff}}$ generated by $\mathbf{A}$. (See Appendices
A.1 and A.2 for the definitions of $\mathscr{Q}_{\operatorname{conv}}$ and
$\mathscr{Z}_{\operatorname{aff}}$, respectively.) In particular, given a
relational structure $\mathbf{X}$ with signature $\sigma$,
$\operatorname{BLP}$ accepts $\mathbf{X}$ as an instance of
$\operatorname{CSP}(\mathbf{A})$ if and only if
$\mathbf{X}\rightarrow\mathbb{S}(\mathbf{A})$; similarly, $\operatorname{AIP}$
accepts $\mathbf{X}$ as an instance of $\operatorname{CSP}(\mathbf{A})$ if and
only if $\mathbf{X}\rightarrow\mathbb{Z}(\mathbf{A})$.

######  Remark 27.

The assignment $f:a\mapsto\mathbf{e}_{a}$ for each $a\in A$ yields both a
canonical homomorphism from $\mathbf{A}$ to $\mathbb{S}(\mathbf{A})$ and a
canonical homomorphism from $\mathbf{A}$ to $\mathbb{Z}(\mathbf{A})$. Indeed,
for $R\in\sigma$ of arity $k$ and $\mathbf{a}=(a_{1},\dots,a_{k})\in
R^{\mathbf{A}}$,

$\displaystyle
f(\mathbf{a})=(\mathbf{e}_{a_{1}},\dots,\mathbf{e}_{a_{k}})=({{E}^{(R^{\mathbf{A}},1)}}\mathbf{e}_{\mathbf{a}},\dots,{{E}^{(R^{\mathbf{A}},k)}}\mathbf{e}_{\mathbf{a}})$

which belongs to both $R^{\mathbb{S}(\mathbf{A})}$ and
$R^{\mathbb{Z}(\mathbf{A})}$ since
$\mathbf{e}_{\mathbf{a}}\in\mathbb{S}(R^{\mathbf{A}})\cap\mathbb{Z}(R^{\mathbf{A}})$.

In Proposition 29, we characterise the instances of a given PCSP template for
which the $\operatorname{CLAP}$ algorithm returns yes in terms of the
condition described in the following definition.

######  Definition 28.

Let $(\mathbf{A},\mathbf{B})$ be a PCSP template, where $\mathbf{A}$ and
$\mathbf{B}$ have signature $\sigma$. Given an instance $\mathbf{X}$ of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, we say that $\mathbf{X}$ has the
$\operatorname{CLAP}$ _condition_ if the following holds: $\forall R\in\sigma$
of arity $k$ $\exists
s^{R}:R^{\mathbf{X}}\rightarrow\operatorname{\mathcal{P}}(R^{\mathbf{A}})\setminus\\{\emptyset\\}$
such that

  * $(I)$

$\forall\mathbf{x}=(x_{1},\dots,x_{k})\in
R^{\mathbf{X}},\forall\mathbf{a}=(a_{1},\dots,a_{k})\in s^{R}(\mathbf{x})$
there is a homomorphism
$h_{\mathbf{x},\mathbf{a}}:\mathbf{X}\rightarrow\mathbb{S}(\mathbf{A})$ that
satisfies:

    1. 1.

$h_{\mathbf{x},\mathbf{a}}(x_{i})=\mathbf{e}_{a_{i}}$ $\forall i\in[k]$;

    2. 2.

$\forall\tilde{R}\in\sigma$ of arity $\tilde{k}$,
$\forall\tilde{\mathbf{x}}=(\tilde{x}_{1},\dots,\tilde{x}_{\tilde{k}})\in\tilde{R}^{\mathbf{X}}$
$\exists\bm{\xi}\in\mathbb{S}(\tilde{R}^{\mathbf{A}})$ such that

       * $\ast$

$h_{\mathbf{x},\mathbf{a}}(\tilde{x}_{i})={{E}^{(\tilde{R}^{\mathbf{A}},i)}}\bm{\xi}\hskip
56.9055pt\forall i\in[\tilde{k}]$;

       * $\ast$

$\operatorname{supp}(\bm{\xi})\subseteq s^{\tilde{R}}(\tilde{\mathbf{x}})$.

  * $(II)$

$\exists\bar{R}\in\sigma,\bar{\mathbf{x}}\in\bar{R}^{\mathbf{X}},\bar{\mathbf{a}}\in
s^{\bar{R}}(\bar{\mathbf{x}})$ such that there is a homomorphism
$g:\mathbf{X}\rightarrow\mathbb{Z}(\mathbf{A})$ that satisfies:

    * $1^{\prime}.$

$\forall\tilde{R}\in\sigma$ of arity $\tilde{k}$,
$\forall\tilde{\mathbf{x}}=(\tilde{x}_{1},\dots,\tilde{x}_{\tilde{k}})\in\tilde{R}^{\mathbf{X}}$
$\exists\bm{\xi}\in\mathbb{S}(\tilde{R}^{\mathbf{A}})$,
$\exists\bm{\zeta}\in\mathbb{Z}(\tilde{R}^{\mathbf{A}})$ such that

      * $\ast$

$h_{\bar{\mathbf{x}},\bar{\mathbf{a}}}(\tilde{x}_{i})={{E}^{(\tilde{R}^{\mathbf{A}},i)}}\bm{\xi}\hskip
56.9055pt\forall i\in[\tilde{k}]$;

      * $\ast$

$g(\tilde{x}_{i})={{E}^{(\tilde{R}^{\mathbf{A}},i)}}\bm{\zeta}\hskip
69.42479pt\forall i\in[\tilde{k}]$;

      * $\ast$

$\operatorname{supp}(\bm{\zeta})\subseteq\operatorname{supp}(\bm{\xi})\subseteq
s^{\tilde{R}}(\tilde{\mathbf{x}})$.

######  Proposition 29.

Given an instance $\mathbf{X}$ of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, $\operatorname{CLAP}$ accepts
$\mathbf{X}$ if and only if $\mathbf{X}$ has the $\operatorname{CLAP}$
condition.

###### Proof.

Suppose that $\operatorname{CLAP}$ accepts $\mathbf{X}$ and let
$\\{S_{\mathbf{x},R}:R\in\sigma,\mathbf{x}\in R^{\mathbf{X}}\\}$ be the family
of sets generated by the algorithm at termination. For each $R\in\sigma$,
consider the map
$s^{R}:R^{\mathbf{X}}\rightarrow\operatorname{\mathcal{P}}(R^{\mathbf{A}})\setminus\\{\emptyset\\}$
defined by $s^{R}(\mathbf{x})=S_{\mathbf{x},R}$. For each $\mathbf{x}\in
R^{\mathbf{X}},\mathbf{a}\in s^{R}(\mathbf{x})$, consider the corresponding
solution to $\operatorname{BLP}(\mathbf{X},\mathbf{A})$ generated by the
algorithm. Letting $w_{x}$ be the probability distribution on $A$ associated
with $x\in X$ in the linear program, we observe that the assignment $x\mapsto
w_{x}$ yields a homomorphism (call it $h_{\mathbf{x},\mathbf{a}}$) from
$\mathbf{X}$ to $\mathbb{S}(\mathbf{A})$ that satisfies the requirement $1$.
Moreover, letting $\bm{\xi}$ be the probability distribution associated with a
constraint $\tilde{\mathbf{x}}\in\tilde{R}^{\mathbf{X}}$ for some
$\tilde{R}\in\sigma$, observe that $h_{\mathbf{x},\mathbf{a}}$ also satisfies
the requirement $2$. Finally, let
$\bar{R}\in\sigma,\bar{\mathbf{x}}\in\bar{R}^{\mathbf{X}},\bar{\mathbf{a}}\in
S_{\bar{\mathbf{x}},\bar{R}}$ be such that the condition in the if statement
of line 15 of Algorithm 1 is met. Then $1^{\prime}$ follows from the
description of $\operatorname{BLP}+\operatorname{AIP}$.

The converse implication follows almost analogously, except for the following
subtlety. The $\operatorname{BLP}+\operatorname{AIP}$ algorithm requires that
the $\operatorname{BLP}$ solution should be picked from the _relative
interior_ of the polytope of the feasible solutions (cf. Algorithm 2 in
Appendix A.3). However, the homomorphism
$h_{\bar{\mathbf{x}},\bar{\mathbf{a}}}$ whose existence witnesses part $(II)$
of the $\operatorname{CLAP}$ condition may correspond to a
$\operatorname{BLP}$ solution that is not in the relative interior of the
polytope $P$ of the feasible solutions of
$\operatorname{BLP}(\mathbf{X},\mathbf{A})$ satisfying
$\lambda_{\bar{\mathbf{x}},\bar{R}}(\bar{\mathbf{a}})=1$ and
$\lambda_{\mathbf{x}^{\prime},R^{\prime}}(\mathbf{a}^{\prime})=0$ for every
$R^{\prime}\in\sigma$, $\mathbf{x}^{\prime}\in R^{\prime\mathbf{X}}$, and
$\mathbf{a}^{\prime}\not\in S_{\mathbf{x}^{\prime},R^{\prime}}$. If that is
the case, the algorithm would not consider
$(h_{\bar{\mathbf{x}},\bar{\mathbf{a}}},g)$ as a solution for
$\operatorname{BLP}+\operatorname{AIP}$. However, letting $h^{\prime}$ be a
solution in the relative interior of $P$, the conditions $(I)$ and $(II)$ of
$\operatorname{CLAP}$ are still satisfied if we let $h^{\prime}$ replace
$h_{\bar{\mathbf{x}},\bar{\mathbf{a}}}$; and, in this case, the homomorphisms
witnessing the $\operatorname{CLAP}$ condition do correspond to solutions
found by the $\operatorname{CLAP}$ algorithm.888Another way to phrase this is
by saying that the existence of a pair $(h,g)$ of homomorphisms such that each
variable for $g$ is zero whenever the corresponding variable for $h$ is zero
is equivalent to the existence, for _any_ $h^{\prime}$ in the nonempty
relative interior of the polytope of solutions of the $\operatorname{BLP}$, of
a solution $g^{\prime}$ of $\operatorname{AIP}$ that sets to zero any variable
that is zero in $h^{\prime}$. This is implicit in the analysis in [22]. Hence,
$\operatorname{CLAP}$ accepts $\mathbf{X}$. ∎

###  4.4 Proof of Theorem 13

Our first goal is to prove the following.

######  Theorem 30.

If there is a minion homomorphism from $\mathscr{C}$ to
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ then $\operatorname{CLAP}$ solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$.

###### Proof.

Let $\mathbf{X}$ be an instance of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$.

First we show that if $\mathbf{X}\to\mathbf{A}$ then $\operatorname{CLAP}$
accepts $\mathbf{X}$, which is the easy direction. Consider a homomorphism
$f:\mathbf{X}\rightarrow\mathbf{A}$. Given $R\in\sigma$ of arity $k$ and
$\mathbf{x}=(x_{1},\dots,x_{k})\in R^{\mathbf{X}}$, let
$s^{R}(\mathbf{x})=\\{f(\mathbf{x})\\}$. For $\mathbf{x}\in R^{\mathbf{X}}$
and $\mathbf{a}=(a_{1},\dots,a_{k})=f(\mathbf{x})\in s^{R}(\mathbf{x})$, let
$h_{\mathbf{x},\mathbf{a}}:\mathbf{X}\rightarrow\mathbb{S}(\mathbf{A})$ be the
homomorphism obtained by composing $f$ with the canonical homomorphism from
$\mathbf{A}$ to $\mathbb{S}(\mathbf{A})$ of Remark 27 – i.e.,
$h_{\mathbf{x},\mathbf{a}}(x)=\mathbf{e}_{f(x)}$ $\forall x\in X$. Observe
that
$h_{\mathbf{x},\mathbf{a}}(x_{i})=\mathbf{e}_{f(x_{i})}=\mathbf{e}_{a_{i}}$
for any $i\in[k]$ and, given $\tilde{R}\in\sigma$ of arity $\tilde{k}$ and
$\tilde{\mathbf{x}}=(\tilde{x}_{1},\dots,\tilde{x}_{\tilde{k}})\in\tilde{R}^{\mathbf{X}}$,
setting $\bm{\xi}=\mathbf{e}_{f(\tilde{\mathbf{x}})}$ yields
$h_{\mathbf{x},\mathbf{a}}(\tilde{x}_{i})=\mathbf{e}_{f(\tilde{x}_{i})}={{E}^{(\tilde{R}^{\mathbf{A}},i)}}\mathbf{e}_{f(\tilde{\mathbf{x}})}={{E}^{(\tilde{R}^{\mathbf{A}},i)}}\bm{\xi}$
for any $i\in[\tilde{k}]$, and
$\operatorname{supp}(\bm{\xi})=\operatorname{supp}(\mathbf{e}_{f(\tilde{\mathbf{x}})})=\\{f(\tilde{\mathbf{x}})\\}=s^{\tilde{R}}(\tilde{\mathbf{x}})$.
This shows that part $(I)$ of Definition 28 is satisfied. As for part $(II)$,
choose any $\bar{R}\in\sigma$ and $\bar{\mathbf{x}}\in\bar{R}^{\mathbf{X}}$,
let $\bar{\mathbf{a}}=f(\bar{\mathbf{x}})$, and consider the homomorphism
$g:\mathbf{X}\rightarrow\mathbb{Z}(\mathbf{A})$ obtained by composing $f$ with
the canonical homomorphism from $\mathbf{A}$ to $\mathbb{Z}(\mathbf{A})$ of
Remark 27 – i.e., $g(x)=\mathbf{e}_{f(x)}$ $\forall x\in X$. Given
$\tilde{R}\in\sigma$ of arity $\tilde{k}$ and
$\tilde{\mathbf{x}}=(\tilde{x}_{1},\dots,\tilde{x}_{\tilde{k}})\in\tilde{R}^{\mathbf{X}}$,
setting $\bm{\xi}=\bm{\zeta}=\mathbf{e}_{f(\tilde{\mathbf{x}})}$ yields
$g(\tilde{x_{i}})=h_{\bar{\mathbf{x}},\bar{\mathbf{a}}}(\tilde{x}_{i})=\mathbf{e}_{f(\tilde{x}_{i})}={{E}^{(\tilde{R}^{\mathbf{A}},i)}}\mathbf{e}_{f(\tilde{\mathbf{x}})}={{E}^{(\tilde{R}^{\mathbf{A}},i)}}\bm{\xi}={{E}^{(\tilde{R}^{\mathbf{A}},i)}}\bm{\zeta}$
for any $i\in[\tilde{k}]$, and
$\operatorname{supp}(\bm{\zeta})=\operatorname{supp}(\bm{\xi})=\\{f(\tilde{\mathbf{x}})\\}=s^{\tilde{R}}(\tilde{\mathbf{x}})$.
It follows that $\mathbf{X}$ has the $\operatorname{CLAP}$ condition. By
Proposition 29, $\operatorname{CLAP}$ accepts $\mathbf{X}$.

Second we show that if $\mathbf{X}$ is accepted by $\operatorname{CLAP}$ then
$\mathbf{X}\to\mathbf{B}$. So, suppose that $\mathbf{X}$ is accepted by
$\operatorname{CLAP}$. By Proposition 29, $\mathbf{X}$ has the
$\operatorname{CLAP}$ condition. Using the terminology of Definition 28,
consider the set
$\\{h_{1},\dots,h_{t}\\}=\\{h_{\mathbf{x},\mathbf{a}}:R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\mathbf{a}\in s^{R}(\mathbf{x})\\}$, where each
$h_{\mathbf{x},\mathbf{a}}$ is a homomorphism from $\mathbf{X}$ to
$\mathbb{S}(\mathbf{A})$ described in part $(I)$ of the definition. We also
consider the homomorphism $g:\mathbf{X}\rightarrow\mathbb{Z}(\mathbf{A})$ of
part $(II)$ of the definition, corresponding to
$\bar{R}\in\sigma,\bar{\mathbf{x}}\in\bar{R}^{\mathbf{X}},\bar{\mathbf{a}}\in
s^{\bar{R}}(\bar{\mathbf{x}})$. Without loss of generality, we set
$h_{1}=h_{\bar{\mathbf{x}},\bar{\mathbf{a}}}$.

Let $n=|A|$. Given $x\in X$, consider the matrix
$M_{x}\in\mathbb{Q}^{n,\aleph_{0}}$ and the vector
$\bm{\mu}_{x}\in\mathbb{Z}^{n}$ defined by

$\displaystyle\begin{array}[]{ll}M_{x}\mathbf{e}_{i}=h_{i}(x)&\forall
i\in[t],\\\ M_{x}\mathbf{e}_{i}=h_{t}(x)&\forall
i\in\mathbb{N}\setminus[t],\\\ \bm{\mu}_{x}=g(x).&\end{array}$

We claim that $(M_{x},\bm{\mu}_{x})\in\mathscr{C}^{(n)}$. The requirements
$(c_{1}),(c_{2}),(c_{3})$, and $(c_{5})$ in Definition 12 are easily seen to
be satisfied. To check that $M_{x}$ is skeletal, take $a\in A$ and suppose
that $\mathbf{e}_{a}^{T}M_{x}\neq\mathbf{0}_{\aleph_{0}}^{T}$. This means that
$\mathbf{e}_{a}^{T}M_{x}\mathbf{e}_{d}\neq 0$ for some $d\in[t]$. Hence,
$a\in\operatorname{supp}(M_{x}\mathbf{e}_{d})=\operatorname{supp}(h_{d}(x))$.
Recall that we are assuming (with no loss of generality) that the signature
$\sigma$ of $\mathbf{X}$, $\mathbf{A}$, and $\mathbf{B}$ contains a unary
symbol $R_{\operatorname{u}}$ such that $R_{\operatorname{u}}^{\mathbf{X}}=X$,
$R_{\operatorname{u}}^{\mathbf{A}}=A$ , and
$R_{\operatorname{u}}^{\mathbf{B}}=B$. Notice that
${E}^{(R_{\operatorname{u}}^{\mathbf{A}},1)}=I_{n}$. From part $(I)$ of
Definition 28, we deduce that $\operatorname{supp}(h_{d}(x))\subseteq
s^{R_{\operatorname{u}}}(x)$ and, hence, $a\in s^{R_{\operatorname{u}}}(x)$.
We can then take the homomorphism $h_{i}=h_{x,a}$, which satisfies
$h_{i}(x)=\mathbf{e}_{a}$, that is $M_{x}\mathbf{e}_{i}=\mathbf{e}_{a}$. So,
$M_{x}$ is skeletal and $(c_{6})$ is satisfied. Finally, to check $(c_{4})$,
choose $a\in A$ and suppose that $\mathbf{e}_{a}^{T}M_{x}\mathbf{e}_{1}=0$.
Since $M_{x}\mathbf{e}_{1}=h_{1}(x)=h_{\bar{\mathbf{x}},\bar{\mathbf{a}}}(x)$,
this implies that
$a\not\in\operatorname{supp}(h_{\bar{\mathbf{x}},\bar{\mathbf{a}}}(x))$.
Choosing $R_{\operatorname{u}}$ as $\tilde{R}$ and $x$ as $\tilde{\mathbf{x}}$
in $1^{\prime}$ of Definition 28, and using again the fact that
${E}^{(R_{\operatorname{u}}^{\mathbf{A}},1)}=I_{n}$, we see that
$\operatorname{supp}(g(x))\subseteq\operatorname{supp}(h_{\bar{\mathbf{x}},\bar{\mathbf{a}}}(x))$.
Therefore,
$a\not\in\operatorname{supp}(g(x))=\operatorname{supp}(\bm{\mu}_{x})$. Hence,
$(c_{4})$ is satisfied, too, and the claim is proved.

Consider the map $\gamma:X\rightarrow\mathscr{C}^{(n)}$ defined by
$x\mapsto(M_{x},\bm{\mu}_{x})$. We claim that $\gamma$ is a homomorphism from
$\mathbf{X}$ to $\mathbb{F}_{\mathscr{C}}(\mathbf{A})$. With this claim, we
can finish the proof. By assumption, there is a minion homomorphism from
$\mathscr{C}$ to $\operatorname{Pol}(\mathbf{A},\mathbf{B})$. By Lemma 22
applied to $\mathscr{C}$, we have
$\mathbb{F}_{\mathscr{C}}(\mathbf{A})\to\mathbf{B}$. Composing $\gamma$ with
this homomorphism yields $\mathbf{X}\rightarrow\mathbf{B}$, as required. It
remains to establish the claim.

Claim: $\gamma$ is a homomorphism from $\mathbf{X}$ to
$\mathbb{F}_{\mathscr{C}}(\mathbf{A})$.

Take $R\in\sigma$ of arity $k$, and let $\mathbf{x}=(x_{1},\dots,x_{k})\in
R^{\mathbf{X}}$. We need to show that
$((M_{x_{1}},\bm{\mu}_{x_{1}}),\dots,\allowbreak(M_{x_{k}},\bm{\mu}_{x_{k}}))\in
R^{\mathbb{F}_{\mathscr{C}}(\mathbf{A})}$. For each $i\in[t]\setminus\\{1\\}$,
consider a probability distribution
$\bm{\xi}_{i}\in\mathbb{S}(R^{\mathbf{A}})$ corresponding to the homomorphism
$h_{i}$ and witnessing part $2$ in Definition 28. Also, consider the
probability distribution $\bm{\xi}_{1}\in\mathbb{S}(R^{\mathbf{A}})$ and the
integer distribution $\bm{\zeta}\in\mathbb{Z}(R^{\mathbf{A}})$ corresponding
to $h_{1}$ and $g$, respectively, and witnessing $1^{\prime}$. We introduce
the matrix $Q\in\mathbb{Q}^{|R^{\mathbf{A}}|,\aleph_{0}}$ and the vector
$\bm{\delta}\in\mathbb{Z}^{|R^{\mathbf{A}}|}$ defined by

$\displaystyle\begin{array}[]{ll}Q\mathbf{e}_{i}=\bm{\xi}_{i}&\forall
i\in[t],\\\ Q\mathbf{e}_{i}=\bm{\xi}_{t}&\forall
i\in\mathbb{N}\setminus[t],\\\ \bm{\delta}=\bm{\zeta}.\end{array}$

We claim that $(Q,\bm{\delta})\in\mathscr{C}^{(|R^{\mathbf{A}}|)}$. The
requirements $(c_{1}),(c_{2}),(c_{3})$, and $(c_{5})$ in Definition 12 are
easily seen to be satisfied. Suppose
$\mathbf{e}_{\mathbf{a}}^{T}Q\neq\mathbf{0}_{\aleph_{0}}^{T}$ for some
$\mathbf{a}=(a_{1},\dots,a_{k})\in R^{\mathbf{A}}$, so that there exists
$d\in[t]$ such that $\mathbf{e}_{\mathbf{a}}^{T}Q\mathbf{e}_{d}\neq 0$. Hence,
$\mathbf{a}\in\operatorname{supp}(Q\mathbf{e}_{d})=\operatorname{supp}(\bm{\xi}_{d})\subseteq
s^{R}(\mathbf{x})$. Pick $h_{j}=h_{\mathbf{x},\mathbf{a}}$. We have that

$\displaystyle{{E}^{(R^{\mathbf{A}},p)}}\bm{\xi}_{j}=h_{j}(x_{p})=h_{\mathbf{x},\mathbf{a}}(x_{p})=\mathbf{e}_{a_{p}}$
$\displaystyle\forall p\in[k].$

Suppose that $\bm{\xi}_{j}\neq\mathbf{e}_{\mathbf{a}}$. Then,
$\exists\mathbf{a}^{\prime}=(a^{\prime}_{1},\dots,a^{\prime}_{k})\in
R^{\mathbf{A}}$ such that $\mathbf{a}^{\prime}\neq\mathbf{a}$ and
$\mathbf{e}_{\mathbf{a}^{\prime}}^{T}\bm{\xi}_{j}>0$. Choose $q\in[k]$ such
that $a^{\prime}_{q}\neq a_{q}$, and observe that

$\displaystyle
0=\mathbf{e}_{a^{\prime}_{q}}^{T}\mathbf{e}_{a_{q}}=\mathbf{e}_{a^{\prime}_{q}}^{T}{{E}^{(R^{\mathbf{A}},q)}}\bm{\xi}_{j}\geq\mathbf{e}_{\mathbf{a}^{\prime}}^{T}\bm{\xi}_{j}>0,$

which is a contradiction. Hence,
$Q\mathbf{e}_{j}=\bm{\xi}_{j}=\mathbf{e}_{\mathbf{a}}$. We conclude that $Q$
is skeletal and, therefore, $(c_{6})$ is satisfied. Finally, suppose that
$\mathbf{a}\not\in\operatorname{supp}(Q\mathbf{e}_{1})=\operatorname{supp}(\bm{\xi}_{1})$
for some $\mathbf{a}\in R^{\mathbf{A}}$. Recalling that
$\bm{\xi}_{1}\in\mathbb{S}(R^{\mathbf{A}})$ corresponds to the homomorphism
$h_{1}=h_{\bar{\mathbf{x}},\bar{\mathbf{a}}}$, it follows from $1^{\prime}$
that
$\operatorname{supp}(\bm{\zeta})\subseteq\operatorname{supp}(\bm{\xi}_{1})$.
Hence,
$\mathbf{a}\not\in\operatorname{supp}(\bm{\zeta})=\operatorname{supp}(\bm{\delta})$,
so that $(c_{4})$ is satisfied, too. As a consequence,
$(Q,\bm{\delta})\in\mathscr{C}^{(|R^{\mathbf{A}}|)}$, as claimed.

Now, we need to show that
$(M_{x_{\alpha}},\bm{\mu}_{x_{\alpha}})=(Q,\bm{\delta})_{/\pi_{\alpha}}$ for
each $\alpha\in[k]$, where $\pi_{\alpha}:R^{\mathbf{A}}\rightarrow A$ maps
$\mathbf{a}\in R^{\mathbf{A}}$ to its $\alpha$-th coordinate. Observe first
that, by definition, ${P_{\pi_{\alpha}}}={E}^{(R^{\mathbf{A}},\alpha)}$ for
each $\alpha\in[k]$. We see that

$\displaystyle
Q_{/\pi_{\alpha}}\mathbf{e}_{i}={P_{\pi_{\alpha}}}Q\mathbf{e}_{i}={{E}^{(R^{\mathbf{A}},\alpha)}}Q\mathbf{e}_{i}={{E}^{(R^{\mathbf{A}},\alpha)}}\bm{\xi}_{i}=h_{i}(x_{\alpha})=M_{x_{\alpha}}\mathbf{e}_{i}$
$\displaystyle\mbox{for }i\in[t]$ and $\displaystyle
Q_{/\pi_{\alpha}}\mathbf{e}_{i}={P_{\pi_{\alpha}}}Q\mathbf{e}_{i}={P_{\pi_{\alpha}}}Q\mathbf{e}_{t}=M_{x_{\alpha}}\mathbf{e}_{t}=M_{x_{\alpha}}\mathbf{e}_{i}$
$\displaystyle\mbox{for }i\in\mathbb{N}\setminus[t],$

which yields $Q_{/\pi_{\alpha}}=M_{x_{\alpha}}$. Moreover,

$\displaystyle\bm{\delta}_{/\pi_{\alpha}}={P_{\pi_{\alpha}}}\bm{\delta}={{E}^{(R^{\mathbf{A}},\alpha)}}\bm{\delta}={{E}^{(R^{\mathbf{A}},\alpha)}}\bm{\zeta}=g(x_{\alpha})=\bm{\mu}_{x_{\alpha}}.$

It follows that
$(M_{x_{\alpha}},\bm{\mu}_{x_{\alpha}})=(Q_{/\pi_{\alpha}},\bm{\delta}_{/\pi_{\alpha}})=(Q,\bm{\delta})_{/\pi_{\alpha}}$.
By Definition 21,
$((M_{x_{1}},\bm{\mu}_{x_{1}}),\dots,\linebreak(M_{x_{k}},\bm{\mu}_{x_{k}}))\in
R^{\mathbb{F}_{\mathscr{C}}(\mathbf{A})}$, so
$\gamma:\mathbf{X}\rightarrow\mathbb{F}_{\mathscr{C}}(\mathbf{A})$ is a
homomorphism. ∎

Our second goal is to prove the following.

######  Theorem 31.

If $\operatorname{CLAP}$ solves $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$
then there is a minion homomorphism from $\mathscr{C}$ to
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$.

######  Remark 32.

The proof of Theorem 31 proceeds essentially by establishing that the free
structure $\mathbb{F}_{\mathscr{C}}(\mathbf{A})$ has the $\operatorname{CLAP}$
condition as an instance of $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$.
However, some care is needed when handling Proposition 29, which only applies
to finite structures, while $\mathbb{F}_{\mathscr{C}}(\mathbf{A})$ is not
finite in general. To overcome this problem, we use a compactness argument
tailored to our minion $\mathscr{C}$ discussed in Section 4.2, which follows
the ideas of [8].

We remark that the compactness argument for relational structures in the form
stated in [22, Lemma A.6] does not entirely fit our proof structure, as the
element $(\mathbf{e}_{1}\mathbf{1}_{\aleph_{0}}^{T},\mathbf{e}_{1})$ having
the role of $\bar{\mathbf{x}}$ in Definition 28 does not belong to every
induced substructure of $\mathbb{F}_{\mathscr{C}}(\mathbf{A})$. A different
option would have been to use the general compactness argument known as the
(uncountable version of the) _compactness theorem of logic_ [62], that applies
to all _minion tests_ 999Cf. Remark 33. as derived in [31, Proposition 6]
through [64].

###### Proof of Theorem 31.

Let $n=|A|$. For $D\in\mathbb{N}$, denote
$\mathbb{F}_{{\mathscr{C}}_{D}}(\mathbf{A})$ by $\mathbf{F}$ (where
${\mathscr{C}}_{D}$ is the sub-minion of $\mathscr{C}$ introduced in Section
4.2). Hence, the domain of $\mathbf{F}$ is $\mathscr{C}_{D}^{(n)}$, which is
finite. We claim that $\mathbf{F}$ has the $\operatorname{CLAP}$ condition as
an instance of $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$.

For each $R\in\sigma$ of arity $k$ and for each
${\bm{\tau}}=((M_{1},\bm{\mu}_{1}),\dots,(M_{k},\bm{\mu}_{k}))\in{R}^{\mathbf{F}}$,
take
$(Q_{\bm{\tau}},{\bm{\delta}}_{\bm{\tau}})\in\mathscr{C}_{D}^{(|R^{\mathbf{A}}|)}$
satisfying
$(M_{j},\bm{\mu}_{j})=(Q_{\bm{\tau}},{\bm{\delta}}_{\bm{\tau}})_{/\pi_{j}}$
$\forall j\in[k]$, where $\pi_{j}:R^{\mathbf{A}}\rightarrow A$ maps
$\mathbf{a}\in R^{\mathbf{A}}$ to its $j$-th coordinate; i.e.,
$M_{j}={{E}^{(R^{\mathbf{A}},j)}}Q_{\bm{\tau}}$ and
$\bm{\mu}_{j}={{E}^{(R^{\mathbf{A}},j)}}{\bm{\delta}}_{\bm{\tau}}$ $\forall
j\in[k]$. Given $R\in\sigma$ of arity $k$, consider the map

$\displaystyle s^{R}:{R}^{\mathbf{F}}$
$\displaystyle\rightarrow\operatorname{\mathcal{P}}({R}^{\mathbf{A}})\setminus\\{\emptyset\\}$
$\displaystyle{\bm{\tau}}$
$\displaystyle\mapsto\bigcup_{i\in\mathbb{N}}\operatorname{supp}(Q_{\bm{\tau}}\mathbf{e}_{i}).$

Let us first check part $(I)$ of Definition 28. Pick
${\bm{\tau}}=((M_{1},\bm{\mu}_{1}),\dots,(M_{k},\bm{\mu}_{k}))\in{R}^{\mathbf{F}}$
and $\mathbf{a}=(a_{1},\dots,a_{k})\in s^{R}({\bm{\tau}})$. We have that
$\mathbf{a}\in\operatorname{supp}(Q_{\bm{\tau}}\mathbf{e}_{\alpha})$ for some
$\alpha\in\mathbb{N}$, i.e.,
$\mathbf{e}_{\mathbf{a}}^{T}Q_{\bm{\tau}}\mathbf{e}_{\alpha}\neq 0$. Since
$Q_{\bm{\tau}}$ is skeletal, the set
$L_{{\bm{\tau}},\mathbf{a}}=\\{\ell\in\mathbb{N}:Q_{\bm{\tau}}\mathbf{e}_{\ell}=\mathbf{e}_{\mathbf{a}}\\}$
is nonempty; let
$\ell({\bm{\tau}},\mathbf{a})\coloneqq\min(L_{{\bm{\tau}},\mathbf{a}})$.
Consider the map

$\displaystyle h_{{\bm{\tau}},\mathbf{a}}:\mathscr{C}_{D}^{(n)}$
$\displaystyle\rightarrow\mathbb{S}(A)$
$\displaystyle(\hat{M},\hat{\bm{\mu}})$
$\displaystyle\mapsto\hat{M}\mathbf{e}_{\ell({\bm{\tau}},\mathbf{a})}.$

We claim that $h_{{\bm{\tau}},\mathbf{a}}$ is a homomorphism from $\mathbf{F}$
to $\mathbb{S}(\mathbf{A})$. Take $\tilde{R}\in\sigma$ of arity $\tilde{k}$,
and let
$\tilde{\bm{\tau}}=((\tilde{M}_{1},\tilde{\bm{\mu}}_{1}),\dots,(\tilde{M}_{\tilde{k}},\tilde{\bm{\mu}}_{\tilde{k}}))\in\tilde{R}^{\mathbf{F}}$.
Consider the pair
$(Q_{\tilde{{\bm{\tau}}}},{\bm{\delta}}_{\tilde{{\bm{\tau}}}})\in\mathscr{C}_{D}^{(|\tilde{R}^{\mathbf{A}}|)}$.
We have that

$\displaystyle h_{{\bm{\tau}},\mathbf{a}}(\tilde{{\bm{\tau}}})$
$\displaystyle=(\tilde{M}_{1}\mathbf{e}_{\ell({\bm{\tau}},\mathbf{a})},\dots,\tilde{M}_{\tilde{k}}\mathbf{e}_{\ell({\bm{\tau}},\mathbf{a})})=\left({{E}^{(\tilde{R}^{\mathbf{A}},1)}}Q_{\tilde{{\bm{\tau}}}}\mathbf{e}_{\ell({\bm{\tau}},\mathbf{a})},\dots,{{E}^{(\tilde{R}^{\mathbf{A}},\tilde{k})}}Q_{\tilde{{\bm{\tau}}}}\mathbf{e}_{\ell({\bm{\tau}},\mathbf{a})}\right).$

Since
$Q_{\tilde{{\bm{\tau}}}}\mathbf{e}_{\ell({\bm{\tau}},\mathbf{a})}\in\mathbb{S}(\tilde{R}^{\mathbf{A}})$,
we deduce that
$h_{{\bm{\tau}},\mathbf{a}}(\tilde{{\bm{\tau}}})\in\tilde{R}^{\mathbb{S}(\mathbf{A})}$,
as wanted. Therefore, $h_{{\bm{\tau}},\mathbf{a}}$ is a homomorphism from
$\mathbf{F}$ to $\mathbb{S}(\mathbf{A})$. We now check that the requirements
$1$ and $2$ in Definition 28 are met. The former follows from

$\displaystyle
h_{{\bm{\tau}},\mathbf{a}}((M_{i},\bm{\mu}_{i}))=M_{i}\mathbf{e}_{\ell({\bm{\tau}},\mathbf{a})}={{E}^{(R^{\mathbf{A}},i)}}Q_{\bm{\tau}}\mathbf{e}_{\ell({\bm{\tau}},\mathbf{a})}={{E}^{(R^{\mathbf{A}},i)}}\mathbf{e}_{\mathbf{a}}=\mathbf{e}_{a_{i}}$
$\displaystyle\forall i\in[k].$

To check the latter requirement, take $\tilde{R}\in\sigma$ of arity
$\tilde{k}$ and
$\tilde{\bm{\tau}}=((\tilde{M}_{1},\tilde{\bm{\mu}}_{1}),\dots,(\tilde{M}_{\tilde{k}},\tilde{\bm{\mu}}_{\tilde{k}}))\in\tilde{R}^{\mathbf{F}}$,
and consider $\bm{\xi}\coloneqq
Q_{\tilde{{\bm{\tau}}}}\mathbf{e}_{\ell({\bm{\tau}},\mathbf{a})}$. Observe
that

$\displaystyle\bullet$ $\displaystyle
h_{{\bm{\tau}},\mathbf{a}}((\tilde{M}_{i},\tilde{\bm{\mu}}_{i}))=\tilde{M}_{i}\mathbf{e}_{\ell({\bm{\tau}},\mathbf{a})}={{E}^{(\tilde{R}^{\mathbf{A}},i)}}Q_{\tilde{{\bm{\tau}}}}\mathbf{e}_{\ell({\bm{\tau}},\mathbf{a})}={{E}^{(\tilde{R}^{\mathbf{A}},i)}}\bm{\xi}$
$\displaystyle\forall i\in[\tilde{k}]$ $\displaystyle\bullet$
$\displaystyle\operatorname{supp}(\bm{\xi})=\operatorname{supp}(Q_{\tilde{{\bm{\tau}}}}\mathbf{e}_{\ell({\bm{\tau}},\mathbf{a})})\subseteq\bigcup_{i\in\mathbb{N}}\operatorname{supp}(Q_{\tilde{{\bm{\tau}}}}\mathbf{e}_{i})=s^{\tilde{R}}(\tilde{{\bm{\tau}}}).$

We now check part $(II)$ of Definition 28. Take $R_{\operatorname{u}}$ as
$\bar{R}$, and observe that

$\displaystyle
R_{\operatorname{u}}^{\mathbf{F}}=\\{(M,\bm{\mu})\in\mathscr{C}_{D}^{(n)}:\exists(Q,{\bm{\delta}})\in\mathscr{C}_{D}^{(n)}\mbox{
such that
}M={{E}^{(R_{\operatorname{u}}^{\mathbf{A}},1)}}Q,\bm{\mu}={{E}^{(R_{\operatorname{u}}^{\mathbf{A}},1)}}{\bm{\delta}}\\}=\mathscr{C}_{D}^{(n)},$

where we have used that ${E}^{(R_{\operatorname{u}}^{\mathbf{A}},1)}=I_{n}$.
Consider the element
$\bar{\tau}=(\mathbf{e}_{1}\mathbf{1}_{\aleph_{0}}^{T},\mathbf{e}_{1})\in\mathscr{C}_{D}^{(n)}=R_{\operatorname{u}}^{\mathbf{F}}$.
Using again that ${E}^{(R_{\operatorname{u}}^{\mathbf{A}},1)}=I_{n}$, we see
that $(Q_{\bar{\tau}},{\bm{\delta}}_{\bar{\tau}})=\bar{\tau}$. We obtain

$\displaystyle
s^{R_{\operatorname{u}}}(\bar{\tau})=\bigcup_{i\in\mathbb{N}}\operatorname{supp}(\mathbf{e}_{1}\mathbf{1}_{\aleph_{0}}^{T}\mathbf{e}_{i})=\bigcup_{i\in\mathbb{N}}\operatorname{supp}(\mathbf{e}_{1})=\\{1\\}.$

Hence, we pick $\bar{a}=1$. Notice that

$\displaystyle\ell(\bar{\tau},\bar{a})=\min\\{\ell\in\mathbb{N}:\mathbf{e}_{1}\mathbf{1}_{\aleph_{0}}^{T}\mathbf{e}_{\ell}=\mathbf{e}_{1}\\}=\min\\{\ell\in\mathbb{N}:\mathbf{e}_{1}=\mathbf{e}_{1}\\}=\min\mathbb{N}=1.$

Consider the function

$\displaystyle g:\mathscr{C}_{D}^{(n)}$
$\displaystyle\rightarrow\mathbb{Z}(A)$
$\displaystyle(\hat{M},\hat{\bm{\mu}})$ $\displaystyle\mapsto\hat{\bm{\mu}}.$

Following the same procedure as for $h_{{\bm{\tau}},\mathbf{a}}$, we easily
check that $g$ is a homomorphism from $\mathbf{F}$ to
$\mathbb{Z}(\mathbf{A})$. We now verify that condition $1^{\prime}$ of
Definition 28 is satisfied. Given $\tilde{R}\in\sigma$ of arity $\tilde{k}$
and
$\tilde{{\bm{\tau}}}=((\tilde{M}_{1},\tilde{\bm{\mu}}_{1}),\dots,(\tilde{M}_{\tilde{k}},\tilde{\bm{\mu}}_{\tilde{k}}))\in\tilde{R}^{\mathbf{F}}$,
let $\bm{\xi}\coloneqq
Q_{\tilde{{\bm{\tau}}}}\mathbf{e}_{1}\in\mathbb{S}(\tilde{R}^{\mathbf{A}})$
and
$\bm{\zeta}\coloneqq{\bm{\delta}}_{\tilde{{\bm{\tau}}}}\in\mathbb{Z}(\tilde{R}^{\mathbf{A}})$.
Then, given $i\in[\tilde{k}]$,

  * $\ast$

$\displaystyle
h_{\bar{\tau},\bar{a}}((\tilde{M}_{i},\tilde{\bm{\mu}}_{i}))=\tilde{M}_{i}\mathbf{e}_{\ell(\bar{\tau},\bar{a})}=\tilde{M}_{i}\mathbf{e}_{1}={{E}^{(\tilde{R}^{\mathbf{A}},i)}}Q_{\tilde{{\bm{\tau}}}}\mathbf{e}_{1}={{E}^{(\tilde{R}^{\mathbf{A}},i)}}\bm{\xi}$;

  * $\ast$

$\displaystyle
g((\tilde{M}_{i},\tilde{\bm{\mu}}_{i}))=\tilde{\bm{\mu}}_{i}={{E}^{(\tilde{R}^{\mathbf{A}},i)}}{\bm{\delta}}_{\tilde{{\bm{\tau}}}}={{E}^{(\tilde{R}^{\mathbf{A}},i)}}\bm{\zeta}$;

  * $\ast$

$\displaystyle\operatorname{supp}(\bm{\zeta})=\operatorname{supp}({\bm{\delta}}_{\tilde{{\bm{\tau}}}})\subseteq\operatorname{supp}(Q_{\tilde{{\bm{\tau}}}}\mathbf{e}_{1})=\operatorname{supp}(\bm{\xi})\subseteq\bigcup_{i\in\mathbb{N}}\operatorname{supp}(Q_{\tilde{{\bm{\tau}}}}\mathbf{e}_{i})=s^{\tilde{R}}(\tilde{{\bm{\tau}}})$

where, for the first inclusion in the third line, we have used $(c_{4})$ in
Definition 12.

It follows that $\mathbf{F}$ has the $\operatorname{CLAP}$ condition as an
instance of $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, as claimed. Then,
Proposition 29 implies that $\operatorname{CLAP}$ accepts F. Since, by
hypothesis, $\operatorname{CLAP}$ solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$, we deduce that
$\mathbb{F}_{\mathscr{C}_{D}}(\mathbf{A})=\mathbf{F}\rightarrow\mathbf{B}$. By
Lemma 22, there exists a minion homomorphism from $\mathscr{C}_{D}$ to
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$. Finally, since the set of
polymorphisms of $(\mathbf{A},\mathbf{B})$ of arity $L$ is finite for every
$L\in\mathbb{N}$, Proposition 25 allows us to conclude that there exists a
minion homomorphism from $\mathscr{C}$ to
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$. ∎

######  Remark 33.

It follows from the proofs of Theorems 30 and 31 that $\operatorname{CLAP}$
fits within the framework of _minion tests_ recently introduced in [31]. More
precisely, $\operatorname{CLAP}=\operatorname{Test}_{\mathscr{C}}$, which
means that, for two $\sigma$-structures $\mathbf{X}$ and $\mathbf{A}$,
$\operatorname{CLAP}(\mathbf{X},\mathbf{A})$ accepts if and only if
$\mathbf{X}\to\mathbb{F}_{\mathscr{C}}(\mathbf{A})$. Additionally, it follows
from [31] that $\operatorname{CLAP}$ is a _conic_ minion test, which
essentially means that one can build a progressively tighter hierarchy of
relaxations based on $\operatorname{CLAP}$ whose $k$-th level correctly
classifies all instances of size $k$.

##  5 H-symmetric polymorphisms

This section contains the proof of Theorem 15. We remark that the machinery
developed here can be extended to the more general setting of $H$-block-
symmetric polymorphisms, at the only cost of dealing with a more cumbersome
notation. This is done in Appendix C and results in Theorem 43 – a slightly
stronger version of Theorem 15.

We shall need two helpful lemmas. The first lemma shows a property of
$H$-symmetric functions that will be useful in the proof of Theorem 15.
Throughout this section, without loss of generality, we consider $A=[n]$.

######  Lemma 34.

Let $f:A^{L}\rightarrow B$ be $H$-symmetric for some $m\times n$ tie matrix
$H$, with $m\in\mathbb{N}$. Consider two maps
$\pi,\tilde{\pi}:[L]\rightarrow[n]$ such that
${P_{\pi}}\mathbf{1}_{L}={P_{\tilde{\pi}}}\mathbf{1}_{L}$ and the vector
${P_{\pi}}\mathbf{1}_{L}$ is $H$-tieless. Then

$\displaystyle f_{/\pi}(1,\dots,n)=f_{/\tilde{\pi}}(1,\dots,n).$

###### Proof.

For ${a}\in[n]$, we have

$\displaystyle|\pi^{-1}({a})|=\sum_{i\in[L]}({P_{\pi}})_{{a}i}=\sum_{i\in[L]}\mathbf{e}_{a}^{T}{P_{\pi}}\mathbf{e}_{i}=\mathbf{e}_{a}^{T}{P_{\pi}}\mathbf{1}_{L}=\mathbf{e}_{a}^{T}{P_{\tilde{\pi}}}\mathbf{1}_{L}=|\tilde{\pi}^{-1}({a})|.$

Hence, we can consider bijections
$\varphi_{a}:\pi^{-1}({a})\rightarrow\tilde{\pi}^{-1}({a})$ for each
${a}\in[n]$. Clearly, their union

$\displaystyle\varphi=\bigcup_{{a}\in[n]}\varphi_{a}:[L]\rightarrow[L]$

is also a bijection. For each $i\in[L]$, we have

$\displaystyle(\tilde{\pi}\circ\varphi)(i)=\tilde{\pi}(\varphi(i))=\tilde{\pi}(\varphi_{\pi(i)}(i))=\pi(i)$

and, hence, $\tilde{\pi}\circ\varphi=\pi$. Let
$\tilde{\mathbf{a}}=(\tilde{\pi}(1),\dots,\tilde{\pi}(L))$. Notice that, for
each $a\in[n]$,

$\displaystyle\mathbf{e}_{a}^{T}\tilde{\mathbf{a}}^{\\#}=|\\{i\in[L]:\tilde{\pi}(i)=a\\}|=\mathbf{e}_{a}^{T}{P_{\tilde{\pi}}}\mathbf{1}_{L}$

and, therefore,
$\tilde{\mathbf{a}}^{\\#}={P_{\tilde{\pi}}}\mathbf{1}_{L}={P_{\pi}}\mathbf{1}_{L}$,
which is $H$-tieless. Using that $f$ is $H$-symmetric, we find

$\displaystyle
f_{/\tilde{\pi}}(1,\dots,n)=f(\tilde{\mathbf{a}})=f_{/\varphi}(\tilde{\mathbf{a}})=(f_{/\varphi})_{/\tilde{\pi}}(1,\dots,n)=f_{/\tilde{\pi}\circ\varphi}(1,\dots,n)=f_{/\pi}(1,\dots,n),$

as required. ∎

One intriguing property of skeletal matrices is that they can be
simultaneously reduced to $H$-tieless vectors, in the sense of the next lemma.
We say that a vector is _finitely supported_ if it only has a finite number of
nonzero entries.

######  Lemma 35 (Tiebreak Lemma).

For $k,p,m\in\mathbb{N}$, let $M_{1},\dots,M_{k}\in\mathbb{Q}^{p,\aleph_{0}}$
be skeletal matrices, and let $H$ be an $m\times p$ tie matrix. Then there
exists a stochastic finitely supported vector
$\mathbf{v}\in\mathbb{Q}^{\aleph_{0}}$ with $\mathbf{e}_{1}^{T}\mathbf{v}>0$
such that $M_{j}\mathbf{v}$ is $H$-tieless for any $j\in[k]$.

###### Proof.

Let $\Omega$ be the set of rational stochastic finitely supported vectors of
size ${\aleph_{0}}$ whose first entry is nonzero, and consider the map

$\displaystyle f:\Omega$ $\displaystyle\rightarrow\mathbb{N}_{0}$
$\displaystyle\hat{\mathbf{v}}$
$\displaystyle\mapsto\sum_{j\in[k]}|\\{(i,i^{\prime})\in[m]^{2}:i\neq
i^{\prime}\mbox{ and
}\mathbf{e}_{i}^{T}HM_{j}\hat{\mathbf{v}}=\mathbf{e}_{i^{\prime}}^{T}HM_{j}\hat{\mathbf{v}}\neq
0\\}|.$

In other words, $f(\hat{\mathbf{v}})$ counts the total number of ties in the
set of vectors $\\{HM_{j}\hat{\mathbf{v}}:j\in[k]\\}$. Let $\mathbf{v}$ attain
the minimum of $f$ over $\Omega$. If $f(\mathbf{v})=0$, we are done.
Otherwise, let $j\in[k]$, $i,i^{\prime}\in[m]$ be such that $i\neq i^{\prime}$
and
$\mathbf{e}_{i}^{T}HM_{j}\mathbf{v}=\mathbf{e}_{i^{\prime}}^{T}HM_{j}\mathbf{v}\neq
0$. From $\mathbf{e}_{i}^{T}HM_{j}\mathbf{v}\neq 0$, we see that
$\exists\beta\in[p]$ such that $\mathbf{e}_{i}^{T}H\mathbf{e}_{\beta}\neq 0$
and $\mathbf{e}_{\beta}^{T}M_{j}\mathbf{v}\neq 0$. In particular, we have
$\mathbf{e}_{\beta}^{T}M_{j}\neq\mathbf{0}_{\aleph_{0}}^{T}$; since $M_{j}$ is
skeletal, this implies that $M_{j}\mathbf{e}_{\alpha}=\mathbf{e}_{\beta}$ for
some $\alpha\in\mathbb{N}$. For $\epsilon\in\mathbb{Q}$, $0<\epsilon<1$,
consider the vector
$\mathbf{v}_{\epsilon}=(1-\epsilon)\mathbf{v}+\epsilon\mathbf{e}_{\alpha}$.
Observe that $\mathbf{v}_{\epsilon}\in\Omega$. For $g\in[k]$, we have
$HM_{g}\mathbf{v}_{\epsilon}=(1-\epsilon)HM_{g}\mathbf{v}+\epsilon
HM_{g}\mathbf{e}_{\alpha}$. By choosing $\epsilon$ sufficiently small, we can
assume that, for each $g\in[k]$, $HM_{g}\mathbf{v}_{\epsilon}$ does not have
new ties other than those in $HM_{g}\mathbf{v}$. Moreover,

$\displaystyle HM_{j}\mathbf{v}_{\epsilon}$
$\displaystyle=(1-\epsilon)HM_{j}\mathbf{v}+\epsilon
HM_{j}\mathbf{e}_{\alpha}=(1-\epsilon)HM_{j}\mathbf{v}+\epsilon
H\mathbf{e}_{\beta}$ and, hence,
$\displaystyle\mathbf{e}_{i}^{T}HM_{j}\mathbf{v}_{\epsilon}$
$\displaystyle=(1-\epsilon)\mathbf{e}_{i}^{T}HM_{j}\mathbf{v}+\epsilon\mathbf{e}_{i}^{T}H\mathbf{e}_{\beta}=(1-\epsilon)\mathbf{e}_{i^{\prime}}^{T}HM_{j}\mathbf{v}+\epsilon\mathbf{e}_{i}^{T}H\mathbf{e}_{\beta}$
$\displaystyle\neq(1-\epsilon)\mathbf{e}_{i^{\prime}}^{T}HM_{j}\mathbf{v}+\epsilon\mathbf{e}_{i^{\prime}}^{T}H\mathbf{e}_{\beta}=\mathbf{e}_{i^{\prime}}^{T}HM_{j}\mathbf{v}_{\epsilon},$

where the disequality follows from $\mathbf{e}_{i}^{T}H\mathbf{e}_{\beta}\neq
0$ and from the fact that $H\mathbf{e}_{\beta}$ is a tieless vector by the
definition of tie matrix. We conclude that
$f(\mathbf{v}_{\epsilon})<f(\mathbf{v})$, which contradicts our assumption. ∎

######  Theorem (Theorem 15 restated).

Let $(\mathbf{A},\mathbf{B})$ be a PCSP template and suppose
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ contains $H$-symmetric operations
of arbitrarily large arity for some $m\times|A|$ tie matrix $H$,
$m\in\mathbb{N}$. Then there exists a minion homomorphism from $\mathscr{C}$
to $\operatorname{Pol}(\mathbf{A},\mathbf{B})$.

######  Remark 36.

Before proving Theorem 15, we provide some intuition on the construction of
the minion homomorphism whose existence shall establish the result. First, one
fixes an $H$-symmetric polymorphism $f$. Then, the image of an $L$-ary element
$(M,\bm{\mu})$ of $\mathscr{C}$ under the homomorphism is the function that
$(i)$ takes a tuple $(a_{1},\dots,a_{L})$ of variables in $A$ as input, $(ii)$
_deforms_ the tuple by changing the frequency of each variable according to
the information carried by $M$ and $\bm{\mu}$, and $(iii)$ returns as output
the evaluation of $f$ on the deformed tuple. The deformation in step $(ii)$ is
encoded by the map $\varphi$ defined in (4). Essentially, $\varphi$ decides
what frequency to assign to a variable $a_{i}$ on the basis of the weight of
$i$ in the probability distribution $M\mathbf{v}$ – where $\mathbf{v}$ is the
_tie-breaking_ vector from Lemma 35. The integer distribution $\bm{\mu}$ is
also taken into account by $\varphi$, and its role is essentially to fill the
gap between the size of the deformed tuple obtained above and the arity of
$f$. If $\operatorname{Pol}(\mathbf{A},\mathbf{B})$ is rich enough to provide
$H$-symmetric polymorphisms of whichever arity we need, $\bm{\mu}$ is
inessential (cf. Remark 37).

###### Proof of Theorem 15.

For $D\in\mathbb{N}$, consider the subminion $\mathscr{C}_{D}$ of
$\mathscr{C}$ described in Section 4.2. Observe that
$S=\\{M:(M,\bm{\mu})\in\mathscr{C}_{D}^{(n)}\\}$ is a finite set of skeletal
matrices. Therefore, we can apply the Tiebreak Lemma 35 to find a stochastic
finitely supported vector ${\mathbf{v}}\in\mathbb{Q}^{\aleph_{0}}$ with
$\mathbf{e}_{1}^{T}{\mathbf{v}}>0$ such that $M{\mathbf{v}}$ is $H$-tieless
for any $M\in S$. Since ${\mathbf{v}}$ is finitely supported, we can find
$N^{\prime}\in\mathbb{N}$ such that $N^{\prime}{\mathbf{v}}$ has integer
entries. Let $\sigma_{1}^{H}$ denote the largest singular value of $H$ – i.e.,
the square root of the largest eigenvalue of $H^{T}H$. Set
$N=2\lceil\sigma_{1}^{H}+1\rceil D^{2}N^{\prime}$, and let $f$ be an
$H$-symmetric polymorphism of arity ${c}\geq N^{2}$. Write
${c}=N{\alpha}+{\beta}$ with ${\alpha},{\beta}\in\mathbb{N}_{0}$, ${\beta}\leq
N-1$. Note that $N^{2}\leq{c}=N{\alpha}+{\beta}\leq
N{\alpha}+N-1<N({\alpha}+1)$, so $N<{\alpha}+1$ and, hence,
${\beta}<{\alpha}$.

Consider the function

$\displaystyle\xi_{D}:\mathscr{C}_{D}\rightarrow\operatorname{Pol}(\mathbf{A},\mathbf{B})$

defined as follows. Given $L\in\mathbb{N}$ and
$(M,\bm{\mu})\in\mathscr{C}_{D}^{(L)}$, take the map
$\varphi:[{c}]\rightarrow[L]$ such that the corresponding $L\times{c}$ matrix
${P_{\varphi}}$ is

$\displaystyle{P_{\varphi}}=\begin{pmatrix}\mathbf{1}^{T}_{\mathbf{e}_{1}^{T}({\alpha}NM{\mathbf{v}}+{\beta}\bm{\mu})}&\mathbf{0}^{T}&\dots&\mathbf{0}^{T}\\\
\mathbf{0}^{T}&\mathbf{1}^{T}_{\mathbf{e}_{2}^{T}({\alpha}NM{\mathbf{v}}+{\beta}\bm{\mu})}&\dots&\mathbf{0}^{T}\\\
\vdots&\vdots&\ddots&\vdots\\\
\mathbf{0}^{T}&\mathbf{0}^{T}&\dots&\mathbf{1}^{T}_{\mathbf{e}_{L}^{T}({\alpha}NM{\mathbf{v}}+{\beta}\bm{\mu})}\end{pmatrix}.$
(4)

To verify that (4) is well defined, observe first that

$\displaystyle\sum_{i=1}^{L}\mathbf{e}_{i}^{T}({\alpha}NM{\mathbf{v}}+{\beta}\bm{\mu})=\mathbf{1}_{L}^{T}({\alpha}NM{\mathbf{v}}+{\beta}\bm{\mu})={\alpha}N\mathbf{1}_{L}^{T}M{\mathbf{v}}+{\beta}\mathbf{1}_{L}^{T}\bm{\mu}={\alpha}N\mathbf{1}_{\aleph_{0}}^{T}{\mathbf{v}}+{\beta}={\alpha}N+{\beta}={c}.$

Moreover, for each $i\in[L]$,
$\mathbf{e}_{i}^{T}({\alpha}NM{\mathbf{v}}+{\beta}\bm{\mu})=\mathbf{e}_{i}^{T}(2{\alpha}\lceil\sigma_{1}^{H}+1\rceil
D(DM)(N^{\prime}{\mathbf{v}})+{\beta}\bm{\mu})$ is an integer. If
$\mathbf{e}_{i}^{T}({\alpha}NM{\mathbf{v}}+{\beta}\bm{\mu})$ was negative,
then $\mathbf{e}_{i}^{T}\bm{\mu}<0$. By the requirement $(c_{4})$ in
Definition 12, this would imply that $\mathbf{e}_{i}^{T}M\mathbf{e}_{1}>0$
and, hence,
$0<\mathbf{e}_{i}^{T}M\mathbf{e}_{1}\mathbf{e}_{1}^{T}{\mathbf{v}}\leq\mathbf{e}_{i}^{T}M{\mathbf{v}}$.
As a consequence, $\mathbf{e}_{i}^{T}(DM)(N^{\prime}{\mathbf{v}})\geq 1$ so
that

$\displaystyle\mathbf{e}_{i}^{T}({\alpha}NM{\mathbf{v}}+{\beta}\bm{\mu})=2{\alpha}\lceil\sigma_{1}^{H}+1\rceil
D\mathbf{e}_{i}^{T}(DM)(N^{\prime}{\mathbf{v}})+{\beta}\mathbf{e}_{i}^{T}\bm{\mu}\geq
2{\alpha}\lceil\sigma_{1}^{H}+1\rceil
D+{\beta}\mathbf{e}_{i}^{T}\bm{\mu}\geq{\alpha}D-{\beta}D>0,$

which is a contradiction. In conclusion, the numbers
$\mathbf{e}_{i}^{T}({\alpha}NM{\mathbf{v}}+{\beta}\bm{\mu})$ are nonnegative
integers summing up to ${c}$, so (4) is well defined.

We define $\xi_{D}((M,\bm{\mu}))\coloneqq f_{/\varphi}$. Clearly,
$\xi_{D}((M,\bm{\mu}))\in\operatorname{Pol}(\mathbf{A},\mathbf{B})$. We claim
that the map $\xi_{D}$ is a minion homomorphism. It is straightforward to
check that $\xi_{D}$ preserves arities so, to conclude, we need to show that
it also preserves minors. Take $L^{\prime}\in\mathbb{N}$ and choose a map
$\pi:[L]\rightarrow[L^{\prime}]$. Letting
$\tilde{\varphi}:[{c}]\rightarrow[L^{\prime}]$ be the map corresponding to the
matrix

$\displaystyle{P_{\tilde{\varphi}}}=\begin{pmatrix}\mathbf{1}^{T}_{\mathbf{e}_{1}^{T}({\alpha}N{P_{\pi}}M{\mathbf{v}}+{\beta}{P_{\pi}}\bm{\mu})}&\mathbf{0}^{T}&\dots&\mathbf{0}^{T}\\\
\mathbf{0}^{T}&\mathbf{1}^{T}_{\mathbf{e}_{2}^{T}({\alpha}N{P_{\pi}}M{\mathbf{v}}+{\beta}{P_{\pi}}\bm{\mu})}&\dots&\mathbf{0}^{T}\\\
\vdots&\vdots&\ddots&\vdots\\\
\mathbf{0}^{T}&\mathbf{0}^{T}&\dots&\mathbf{1}^{T}_{\mathbf{e}_{L^{\prime}}^{T}({\alpha}N{P_{\pi}}M{\mathbf{v}}+{\beta}{P_{\pi}}\bm{\mu})}\end{pmatrix},$

we see that $\xi_{D}((M,\bm{\mu})_{/\pi})=f_{/\tilde{\varphi}}$. Moreover,
$\xi_{D}((M,\bm{\mu}))_{/\pi}=(f_{/\varphi})_{/\pi}=f_{/\pi\circ\varphi}$,
where $\varphi$ corresponds to the matrix ${P_{\varphi}}$ in (4). Take
${\mathbf{a}}=(a_{1},\dots,a_{L^{\prime}})\in A^{L^{\prime}}$, and consider
the map

$\displaystyle\pi_{\mathbf{a}}:[L^{\prime}]$ $\displaystyle\rightarrow[n]$
$\displaystyle i$ $\displaystyle\mapsto a_{i}.$

Observe that

$\displaystyle f_{/\tilde{\varphi}}(\mathbf{a})$ $\displaystyle=$
$\displaystyle(f_{/\tilde{\varphi}})_{/\pi_{\mathbf{a}}}(1,\dots,n)$
$\displaystyle=$ $\displaystyle
f_{/\pi_{\mathbf{a}}\circ\tilde{\varphi}}(1,\dots,n)$ and, similarly,
$\displaystyle f_{/\pi\circ\varphi}(\mathbf{a})$ $\displaystyle=$
$\displaystyle(f_{/\pi\circ\varphi})_{/\pi_{\mathbf{a}}}(1,\dots,n)$
$\displaystyle=$ $\displaystyle
f_{/\pi_{\mathbf{a}}\circ\pi\circ\varphi}(1,\dots,n).$ (5)

Notice that

$\displaystyle{P_{\pi_{\mathbf{a}}\circ\tilde{\varphi}}}\mathbf{1}_{c}$
$\displaystyle={P_{\pi_{\mathbf{a}}}}{P_{\tilde{\varphi}}}\mathbf{1}_{c}={P_{\pi_{\mathbf{a}}}}({\alpha}N{P_{\pi}}M{\mathbf{v}}+{\beta}{P_{\pi}}\bm{\mu})$
$\displaystyle={P_{\pi_{\mathbf{a}}}}{P_{\pi}}({\alpha}NM{\mathbf{v}}+{\beta}\bm{\mu})={P_{\pi_{\mathbf{a}}}}{P_{\pi}}{P_{\varphi}}\mathbf{1}_{c}={P_{\pi_{\mathbf{a}}\circ\pi\circ\varphi}}\mathbf{1}_{c}.$

We claim that the vector
${P_{\pi_{\mathbf{a}}\circ\tilde{\varphi}}}\mathbf{1}_{c}$ is $H$-tieless. Let
${\mathbf{u}}=(u_{i})=H{P_{\pi_{\mathbf{a}}\circ\tilde{\varphi}}}\mathbf{1}_{c}$;
the claim is equivalent to ${\mathbf{u}}$ being tieless. Let
${\mathbf{w}}=(w_{i})={\alpha}NH{P_{\pi_{\mathbf{a}}\circ\pi}}M{\mathbf{v}}$
and ${\mathbf{z}}=(z_{i})={\beta}H{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}$, so
that ${\mathbf{u}}={\mathbf{w}}+{\mathbf{z}}$. Choose $i,i^{\prime}\in[m]$
such that $i\neq i^{\prime}$ and $u_{i}\neq 0$. We need to show that
$u_{i}\neq u_{i^{\prime}}$. Suppose $w_{i}=0$. We can write
$H^{T}\mathbf{e}_{i}=\sum_{g\in G}\lambda_{g}\mathbf{e}_{g}$ for
$G=\operatorname{supp}(H^{T}\mathbf{e}_{i})$, where each $\lambda_{g}$ is a
positive integer (note that $G\neq\emptyset$ since, otherwise,
$H^{T}\mathbf{e}_{i}=\mathbf{0}_{n}$, which would imply $u_{i}=0$). Let
$F=(\pi_{\mathbf{a}}\circ\pi)^{-1}(G)$. From $w_{i}=0$, we obtain

$\displaystyle
0=\mathbf{e}_{i}^{T}H{P_{\pi_{\mathbf{a}}\circ\pi}}M{\mathbf{v}}=(H^{T}\mathbf{e}_{i})^{T}{P_{\pi_{\mathbf{a}}\circ\pi}}M{\mathbf{v}}$
$\displaystyle=$ $\displaystyle\sum_{g\in
G}\lambda_{g}\mathbf{e}_{g}^{T}{P_{\pi_{\mathbf{a}}\circ\pi}}M{\mathbf{v}}=\sum_{g\in
G}\lambda_{g}\sum_{j\in(\pi_{\mathbf{a}}\circ\pi)^{-1}(g)}\mathbf{e}_{j}^{T}M{\mathbf{v}}$

and, hence, the following chain of implications holds:

$\displaystyle\begin{array}[]{lllll}&\displaystyle 0=\sum_{g\in
G}\sum_{j\in(\pi_{\mathbf{a}}\circ\pi)^{-1}(g)}\mathbf{e}_{j}^{T}M{\mathbf{v}}=\sum_{j\in
F}\mathbf{e}_{j}^{T}M{\mathbf{v}}&\displaystyle\hskip
5.69046pt\Rightarrow&\displaystyle\mathbf{e}_{j}^{T}M{\mathbf{v}}=0&{\forall
j\in F}\\\\[7.0pt]
\Rightarrow&\displaystyle\mathbf{e}_{j}^{T}M\mathbf{e}_{1}=0\hskip
28.45274pt{\forall j\in F}&\hskip
5.69046pt\Rightarrow&\displaystyle\mathbf{e}_{j}^{T}\bm{\mu}=0&{\forall j\in
F}\end{array}$

(where the second implication follows from $\mathbf{e}_{1}^{T}{\mathbf{v}}>0$,
and the third follows from $(c_{4})$ in Definition 12). Hence,

$\displaystyle
z_{i}={\beta}\mathbf{e}_{i}^{T}H{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}={\beta}\sum_{g\in
G}\lambda_{g}\mathbf{e}_{g}^{T}{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}={\beta}\sum_{g\in
G}\lambda_{g}\sum_{j\in(\pi_{\mathbf{a}}\circ\pi)^{-1}(g)}\mathbf{e}_{j}^{T}\bm{\mu}=0,$

so that $u_{i}=w_{i}+z_{i}=0$, a contradiction. Hence, $w_{i}>0$. Observe that
$(M_{/\pi_{\mathbf{a}}\circ\pi},\bm{\mu}_{/\pi_{\mathbf{a}}\circ\pi})\in\mathscr{C}_{D}^{(n)}$
and, hence, $M_{/\pi_{\mathbf{a}}\circ\pi}\in S$. By the choice of
${\mathbf{v}}$, this implies that the vector
${P_{\pi_{\mathbf{a}}\circ\pi}}M{\mathbf{v}}=M_{/\pi_{\mathbf{a}}\circ\pi}{\mathbf{v}}$
is $H$-tieless; i.e., $H{P_{\pi_{\mathbf{a}}\circ\pi}}M{\mathbf{v}}$ is
tieless. It follows that the vector
$H{P_{\pi_{\mathbf{a}}\circ\pi}}(DM)(N^{\prime}{\mathbf{v}})=\frac{1}{2{\alpha}\lceil\sigma_{1}^{H}+1\rceil
D}{\mathbf{w}}$ is also tieless; being it entrywise integer, and since
$\frac{1}{2{\alpha}\lceil\sigma_{1}^{H}+1\rceil D}w_{i}>0$, we obtain

$\displaystyle\left|\frac{1}{2{\alpha}\lceil\sigma_{1}^{H}+1\rceil
D}w_{i}-\frac{1}{2{\alpha}\lceil\sigma_{1}^{H}+1\rceil
D}w_{i^{\prime}}\right|\geq 1$ that yields
$\displaystyle|w_{i}-w_{i^{\prime}}|\geq 2{\alpha}\lceil\sigma_{1}^{H}+1\rceil
D.$

Denote the $\ell_{1}$-norm and the $\ell_{2}$-norm of a vector by
$\|\cdot\|_{1}$ and $\|\cdot\|_{2}$, respectively. Recall that the largest
singular value of a matrix is its spectral operator norm – i.e.,
$\sigma_{1}^{H}=\max_{\mathbf{0}\neq\mathbf{x}\in\mathbb{R}^{n}}\frac{\|H\mathbf{x}\|_{2}}{\|\mathbf{x}\|_{2}}$
(see [47]). In particular,
$\|H\mathbf{x}\|_{2}\leq\sigma_{1}^{H}\|\mathbf{x}\|_{2}$ for each vector
$\mathbf{x}$ of size $n$. Using the Cauchy-Schwarz inequality and the fact
that the $\ell_{1}$-norm of a vector is greater than or equal to its
$\ell_{2}$-norm, we find

$\displaystyle|z_{i}-z_{i^{\prime}}|$
$\displaystyle={\beta}|(\mathbf{e}_{i}-\mathbf{e}_{i^{\prime}})^{T}H{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}|\leq{\beta}\|\mathbf{e}_{i}-\mathbf{e}_{i^{\prime}}\|_{2}\|H{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}\|_{2}\leq{\beta}\|\mathbf{e}_{i}-\mathbf{e}_{i^{\prime}}\|_{2}\sigma_{1}^{H}\|{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}\|_{2}$
$\displaystyle\leq{\beta}\|\mathbf{e}_{i}-\mathbf{e}_{i^{\prime}}\|_{1}\lceil\sigma_{1}^{H}+1\rceil\|{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}\|_{1}=2{\beta}\lceil\sigma_{1}^{H}+1\rceil\mathbf{1}_{n}^{T}|{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}|\leq
2{\beta}\lceil\sigma_{1}^{H}+1\rceil\mathbf{1}_{n}^{T}{P_{\pi_{\mathbf{a}}\circ\pi}}|\bm{\mu}|$
$\displaystyle=2{\beta}\lceil\sigma_{1}^{H}+1\rceil\mathbf{1}_{L}^{T}|\bm{\mu}|\leq
2{\beta}\lceil\sigma_{1}^{H}+1\rceil D<2{\alpha}\lceil\sigma_{1}^{H}+1\rceil
D.$

We conclude the proof of the claim by noting that

$\displaystyle|u_{i}-u_{i^{\prime}}|=|(w_{i}-w_{i^{\prime}})-(z_{i^{\prime}}-z_{i})|\geq|w_{i}-w_{i^{\prime}}|-|z_{i}-z_{i^{\prime}}|>2{\alpha}\lceil\sigma_{1}^{H}+1\rceil
D-2{\alpha}\lceil\sigma_{1}^{H}+1\rceil D=0,$

which implies $u_{i}\neq u_{i^{\prime}}$. As a consequence, the vector
${P_{\pi_{\mathbf{a}}\circ\tilde{\varphi}}}\mathbf{1}_{c}$ is $H$-tieless. We
can then apply Lemma 34 to conclude that
$f_{/\pi_{\mathbf{a}}\circ\tilde{\varphi}}(1,\dots,n)=f_{/\pi_{\mathbf{a}}\circ\pi\circ\varphi}(1,\dots,n)$.
Hence, by (5), $f_{/\tilde{\varphi}}=f_{/\pi\circ\varphi}$. Therefore,
$\xi_{D}((M,\bm{\mu})_{/\pi})=\xi_{D}((M,\bm{\mu}))_{/\pi}$, as required. It
follows that $\xi_{D}$ is a minion homomorphism.

Since the set of polymorphisms of $(\mathbf{A},\mathbf{B})$ of arity $L$ is
finite for every $L\in\mathbb{N}$, we can apply Proposition 25 to conclude
that there exists a minion homomorphism
$\zeta:\mathscr{C}\rightarrow\operatorname{Pol}(\mathbf{A},\mathbf{B})$. ∎

######  Remark 37.

If $\operatorname{Pol}(\mathbf{A},\mathbf{B})$ contains $H$-symmetric
operations of _all_ arities – as it happens for the PCSP template
$(\mathbf{A},\mathbf{B})$ from Example 10, cf. Example 16 – the
$\operatorname{AIP}$ part of $\operatorname{CLAP}$ is not required. Indeed, in
that case, we can choose $f$ in the proof of Theorem 15 to be an $H$-symmetric
polymorphism of arity $c=N^{2}$, which implies $\beta=0$. Therefore, the
affine vector $\bm{\mu}$ does not have any role in the definition of
${P_{\varphi}}$ in (4), nor in the definition of the minion homomorphism
$\xi_{D}$. It follows that, under this stronger hypothesis,
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ admits a minion homomorphism from
a minion $\hat{\mathscr{C}}$ whose $L$-ary elements are matrices in
$\mathbb{Q}^{L,\aleph_{0}}$ satisfying the requirements
$(c_{1}),(c_{2}),(c_{5}),(c_{6})$ of Definition 12; notice that the projection
$(M,\bm{\mu})\mapsto M$ yields a natural minion homomorphism from
$\mathscr{C}$ to $\hat{\mathscr{C}}$. The proofs of Theorems 30 and 31 can be
straightforwardly modified to show that $\hat{\mathscr{C}}$ captures the power
of the algorithm $\operatorname{CBLP}$ – i.e., the simplified version of
$\operatorname{CLAP}$ that does not run
$\operatorname{BLP}+\operatorname{AIP}$ at the end (cf. the discussion in
Section 3).

## Acknowledgements

We would like to thank the anonymous referees of both the conference [32] and
this full version of the paper.

##  Appendix A Existing relaxations for PCSPs

Every CSP can be equivalently expressed as a $0$–$1$ integer program in a
standard way.

If the variables are allowed to take values in $[0,1]$, we obtain the so-
called basic linear programming relaxation ($\operatorname{BLP}$) [59]. This
naturally extends to PCSPs [8], as we describe in Appendix A.1.

If the variables are allowed to take integer values, we obtain the so-called
basic affine integer programming relaxation ($\operatorname{AIP}$) [20],
studied in detail in [8], as we describe in Appendix A.2.

A combination of the two relaxations, called the
$\operatorname{BLP}+\operatorname{AIP}$ relaxation, was proposed in [22] and
its power characterised in [22], as we describe in Appendix A.3.

Let $(\mathbf{A},\mathbf{B})$ be a PCSP template with signature $\sigma$ and
let $\mathbf{X}$ be an instance of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$. In all three relaxations
described below, we assume without loss of generality that $\sigma$ contains a
unary symbol $R_{\operatorname{u}}$ such that
$R_{\operatorname{u}}^{\mathbf{X}}=X$, $R_{\operatorname{u}}^{\mathbf{A}}=A$,
and $R_{\operatorname{u}}^{\mathbf{B}}=B$. If this is not the case, the
signature and the instance can be extended without changing the set of
solutions.

###  A.1 BLP

The _basic linear programming relaxation_ ($\operatorname{BLP}$) of
$\mathbf{X}$, denoted by $\operatorname{BLP}(\mathbf{X},\mathbf{A})$, is
defined as follows.101010The definition does not depend on $\mathbf{B}$ and is
the same as the $\operatorname{BLP}$ of an instance $\mathbf{X}$ of
$\operatorname{CSP}(\mathbf{A})$; the same holds for $\operatorname{AIP}$ and
$\operatorname{BLP}+\operatorname{AIP}$. The variables are
$\lambda_{\mathbf{x},R}(\mathbf{a})$ for every $R\in\sigma$, $\mathbf{x}\in
R^{\mathbf{X}}$, and $\mathbf{a}\in R^{\mathbf{A}}$, and the constraints are
given in Figure 1.

$\displaystyle 0\ \leq\ \lambda_{\mathbf{x},R}(\mathbf{a})\ $
$\displaystyle\leq\ 1$ $\displaystyle\forall R\in\sigma,\forall\mathbf{x}\in
R^{\mathbf{X}},\forall\mathbf{a}\in R^{\mathbf{A}}$
$\displaystyle\sum_{\mathbf{a}\in
R^{\mathbf{A}}}\lambda_{\mathbf{x},R}(\mathbf{a})\ $ $\displaystyle=\ 1$
$\displaystyle\hskip 85.35826pt\forall R\in\sigma,\forall\mathbf{x}\in
R^{\mathbf{X}}$ $\displaystyle\sum_{\mathbf{a}\in
R^{\mathbf{A}},a_{i}=a}\lambda_{\mathbf{x},R}(\mathbf{a})\ $ $\displaystyle=\
\lambda_{x_{i},R_{\operatorname{u}}}(a)$ $\displaystyle\hskip
85.35826pt\forall R\in\sigma,\forall\mathbf{x}\in R^{\mathbf{X}},\forall a\in
A,\forall i\in[\operatorname{ar}(R)]$ Figure 1: Definition of
$\operatorname{BLP}(\mathbf{X},\mathbf{A})$.

We say that $\operatorname{BLP}(\mathbf{X},\mathbf{A})$ accepts if the LP in
Figure 1 is feasible, and rejects otherwise. By construction, if
$\mathbf{X}\to\mathbf{A}$ then $\operatorname{BLP}(\mathbf{X},\mathbf{A})$
accepts. We say that $\operatorname{BLP}$ _solves_
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if for every instance
$\mathbf{X}$ accepted by $\operatorname{BLP}(\mathbf{X},\mathbf{A})$ we have
$\mathbf{X}\to\mathbf{B}$.

We denote by $\mathscr{Q}_{\operatorname{conv}}$ the minion of stochastic
vectors on $\mathbb{Q}$ with the minor operation defined as in Section 4.1;
i.e., if $\mathbf{q}\in\mathscr{Q}_{\operatorname{conv}}^{(L)}$ and
$\pi:[L]\to[L^{\prime}]$, then $\mathbf{q}_{/\pi}={P_{\pi}}\mathbf{q}$, where
$P_{\pi}$ is the $L^{\prime}\times L$ matrix whose $(i,j)$-th entry is $1$ if
$\pi(j)=i$, and $0$ otherwise.

An $L$-ary operation $f:A^{L}\to B$ is called _symmetric_ if
$f(a_{1},\ldots,a_{L})=f(a_{\pi(1)},\ldots,a_{\pi(L)})$ for every
$a_{1},\ldots,a_{L}\in A$ and every permutation $\pi:[L]\to[L]$.

The power of $\operatorname{BLP}$ for PCSPs is characterised in the following
result.

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

Let $(\mathbf{A},\mathbf{B})$ be a PCSP template. The following are
equivalent:

  1. (1)

$\operatorname{BLP}$ solves $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$.

  2. (2)

$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ admits a minion homomorphism from
$\mathscr{Q}_{\operatorname{conv}}$.

  3. (3)

$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ contains symmetric operations of
all arities.

###  A.2 AIP

The _basic affine integer programming relaxation_ ($\operatorname{AIP}$) of
$\mathbf{X}$, denoted by $\operatorname{AIP}(\mathbf{X},\mathbf{A})$, is
defined as follows. The variables are $\tau_{\mathbf{x},R}(\mathbf{a})$ for
every $R\in\sigma$, $\mathbf{x}\in R^{\mathbf{X}}$, and $\mathbf{a}\in
R^{\mathbf{A}}$, and the constraints are given in Figure 2.

$\displaystyle\tau_{\mathbf{x},R}(\mathbf{a})\ $ $\displaystyle\in\
\mathbb{Z}$ $\displaystyle\forall R\in\sigma,\forall\mathbf{x}\in
R^{\mathbf{X}},\forall\mathbf{a}\in R^{\mathbf{A}}$
$\displaystyle\sum_{\mathbf{a}\in
R^{\mathbf{A}}}\tau_{\mathbf{x},R}(\mathbf{a})\ $ $\displaystyle=\ 1$
$\displaystyle\hskip 85.35826pt\forall R\in\sigma,\forall\mathbf{x}\in
R^{\mathbf{X}}$ $\displaystyle\sum_{\mathbf{a}\in
R^{\mathbf{A}},a_{i}=a}\tau_{\mathbf{x},R}(\mathbf{a})\ $ $\displaystyle=\
\tau_{x_{i},R_{\operatorname{u}}}(a)$ $\displaystyle\hskip 85.35826pt\forall
R\in\sigma,\forall\mathbf{x}\in R^{\mathbf{X}},\forall a\in A,\forall
i\in[\operatorname{ar}(R)]$ Figure 2: Definition of
$\operatorname{AIP}(\mathbf{X},\mathbf{A})$.

We say that $\operatorname{AIP}(\mathbf{X},\mathbf{A})$ accepts if the affine
program in Figure 2 is feasible, and rejects otherwise. By construction, if
$\mathbf{X}\to\mathbf{A}$ then $\operatorname{AIP}(\mathbf{X},\mathbf{A})$
accepts. We say that $\operatorname{AIP}$ _solves_
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if for every instance
$\mathbf{X}$ accepted by $\operatorname{AIP}(\mathbf{X},\mathbf{A})$ we have
$\mathbf{X}\to\mathbf{B}$.

We denote by $\mathscr{Z}_{\operatorname{aff}}$ the minion of affine vectors
on $\mathbb{Z}$ with the minor operation defined as in Section 4.1; i.e., if
$\mathbf{z}\in\mathscr{Z}_{\operatorname{aff}}^{(L)}$ and
$\pi:[L]\to[L^{\prime}]$, then $\mathbf{z}_{/\pi}={P_{\pi}}\mathbf{z}$, where
${P_{\pi}}$ is the $L^{\prime}\times L$ matrix whose $(i,j)$-th entry is $1$
if $\pi(j)=i$, and $0$ otherwise.

A $(2L+1)$-ary operation $f:A^{2L+1}\to B$ is called _alternating_ if
$f(a_{1},\ldots,a_{2L+1})=f(a_{\pi(1)},\ldots,\allowbreak a_{\pi(2L+1)})$ for
every $a_{1},\ldots,a_{2L+1}\in A$ and every permutation $\pi:[2L+1]\to[2L+1]$
that preserves parity, and
$f(a_{1},\ldots,a_{2L-1},a,a)=f(a_{1},\ldots,a_{2L-1},a^{\prime},a^{\prime})$
for every $a_{1},\ldots,a_{2L-1},a,a^{\prime}\in A$. Intuitively, an
alternating operation is invariant under permutations of its odd and even
coordinates and has the property that adjacent coordinates cancel each other
out.

The power of $\operatorname{AIP}$ for PCSPs is characterised in the following
result.

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

Let $(\mathbf{A},\mathbf{B})$ be a PCSP template. The following are
equivalent:

  1. (1)

$\operatorname{AIP}$ solves $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$.

  2. (2)

$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ admits a minion homomorphism from
$\mathscr{Z}_{\operatorname{aff}}$.

  3. (3)

$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ contains alternating operations of
all odd arities.

###  A.3 BLP+AIP

The _combined basic LP and affine IP algorithm_
($\operatorname{BLP}+\operatorname{AIP}$) is presented in Algorithm 2.

Input: an instance $\mathbf{X}$ of
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ of signature $\sigma$

Output: yes if $\mathbf{X}\to\mathbf{A}$ and no if
$\mathbf{X}\not\to\mathbf{B}$

1 find a relative interior point
$(\lambda_{\mathbf{x},R}(\mathbf{a}))_{R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\mathbf{a}\in R^{\mathbf{A}}}$ of
$\operatorname{BLP}(\mathbf{X},\mathbf{A})$;

2 if  _no relative interior point exists_ then

3 return no;

4 end if

5refine $\operatorname{AIP}(\mathbf{X},\mathbf{A})$ by setting
$\tau_{\mathbf{x},R}(\mathbf{a})=0$ if $\lambda_{\mathbf{x},R}(\mathbf{a})=0$;

6 if  _the refined $\operatorname{AIP}(\mathbf{X},\mathbf{A})$ accepts_ then

7 return yes;

8 end if

9return no;

Algorithm 2 The $\operatorname{BLP}+\operatorname{AIP}$ algorithm

If $\mathbf{X}\to\mathbf{A}$ then $\operatorname{BLP}+\operatorname{AIP}$