# Solving promise equations over monoids and groups††thanks: This work was
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.

Alberto Larrauri
University of Oxford
<EMAIL_ADDRESS>Stanislav Živný
University of Oxford
<EMAIL_ADDRESS>
(3rd September 2024)

###### Abstract

We give a complete complexity classification for the problem of finding a
solution to a given system of equations over a fixed finite monoid, given that
a solution over a more restricted monoid exists. As a corollary, we obtain a
complexity classification for the same problem over groups.

##  1 Introduction

Constraint satisfaction problems (CSPs) form a large class of fundamental
computational problems studied in artificial intelligence, database theory,
logic, graph theory, and computational complexity. Since CSPs (with infinite
domains) capture, up to polynomial-time Turing reductions, _all_ computational
problems [11], some restrictions need to be imposed on CSPs in order to have a
chance to obtain complexity classifications. One line of work, pioneered in
the database theory [34], restricts the interactions of the constraints in the
instance [29, 38].

Another line of work, pioneered in [32, 25], restricts the types of relations
used in the instance; these CSPs are known as nonuniform CSPs, or as having a
fixed template/constraint language. Such CSPs with infinite domains capture
graph acyclicity, systems of linear equations over the rationals, and many
other problems [10]. Already fixed-template CSPs with finite domains form a
large class of fundamental problems, including graph colourings [31], variants
of the Boolean satisfiability problem, and, more generally, systems of
equations over different types of finite algebraic structures. Even then, the
class of finite-domain CSPs avoided a complete complexity classification for
two decades despite a sustained effort.

In 2017, Bulatov [20] and, independently, Zhuk [44] classified all finite-
domain CSPs as either solvable in polynomial time or -hard, thus answering in
the affirmative the Feder-Vardi dichotomy conjecture [25]. In the effort to
answer the Feder-Vardi conjecture, many complexity dichotomies were
established in restricted fragments of CSPs. This included conservative CSPs
[19], or equations over finite algebraic structures such as semigroups,
groups, and monoids [28, 33]. In particular, while systems of equations111Some
papers use the term a _linear_ equation. over Abelian groups are solvable in
polynomial time, they are -hard over non-Abelian groups [28].

One of the recent research directions in constraint satisfaction that has
attracted a lot of attention is the area of _promise_ CSPs (PCSPs) [3, 13, 5].
The idea is that each constraint comes in pairs, with a strong version and a
weak version. Given an instance, one is promised that a solution satisfying
all strict constraints exists and the goal is to find a solution satisfying
all weak constraints, which may be an easier task. The prototypical example is
the approximate graph colouring problem [27]: Given a $3$-colourable graph,
can one find a $6$-colouring? The complexity of this problem is open (but
believed to be -hard). Despite a flurry of papers on PCSPs, e.g., [26, 1, 4,
17, 40, 41, 6, 2, 21, 14, 15, 23, 22], the PCSP complexity landscape is widely
open and unexplored. It is not even clear whether a dichotomy should be
expected. Even the case of Boolean PCSPs remain open, the state-of-the-art
being a dichotomy for Boolean _symmetric_ PCSPs [26]. This should be compared
with Boolean (non-promise) CSPs, which were classified by Schaefer in 1978
[42]. Schaefer’s tractable cases include the classic and well-known examples
of CSPs: equations and graph colouring. Both have been studied on non-Boolean
domains and their complexity is well understood. However, the complexity of
the promise variant of these fundamental problems is open. The first problem,
graph colouring, leads to the already mentioned approximate graph colouring
problem, which is a notorious open problem, despite recent progress [5, 36].
In this paper, we look at the second problem, and study PCSPs capturing
systems of equations.

Contributions The precise statements of all our main results are presented in
Section 3.

As our most important contribution, in Section 5 we establish a complexity
dichotomy for PCSPs capturing _promise_ systems of equations over monoids, and
over groups as a special case. Perhaps unsurprisingly, the tractability
boundary is linked to the notion of Abelianness, just like in the non-promise
setting, but the result is non-trivial and requires some care. Our main tool
is the “the algebraic approach to PCSPs” [5]. The influential paper [5]
identified _minions_ as an important concept. Minions generalise the notion of
“a family of functions that is closed under permuting arguments, identifying
arguments, and adding dummy arguments”. A crucial example is the polymorphism
minion of a PCSP template. Polymorphisms can be seen as high-dimensional
symmetries of a PCSP template and capture the complexity of the underlying
computational problem [13, 5]. Following the algebraic approach [5], hardness
of a PCSP is established by showing that the associated polymorphism minion
is, in some sense, limited. Conversely, if this minion is rich enough then the
PCSP can be shown to be solvable via some efficient algorithm [5, 16, 22, 15].

To prove our main result, we study a class of minions that arise naturally
from monoids, which we call monoidal minions. In Section 4 we show a
complexity dichotomy for PCSPs whose polymorphism minions are homomorphically
equivalent to some monoidal minion. This is our second contribution, which may
be of independent interest. In particular, the concept of monoidal minions
captures studied minions, cf. Remark 1 in Section 3.

All our tractability results use solvability via the
$\textsc{BLP}+\textsc{AIP}$ algorithm [16]. In fact, tractable PCSPs
corresponding to promise systems of equations over monoids are finitely
tractable in the sense of [13, 1]. In the special case of promise systems of
equations over groups, the affine integer programming (AIP) algorithm [13, 5]
suffices, rather than $\textsc{BLP}+\textsc{AIP}$. However, AIP is provably
not enough to solve promise equations over general monoids.

As our final contribution, in Section 6 we show that our dichotomy for systems
of equations over monoids cannot be easily extended to semigroups, as this
would imply a dichotomy for all PCSPs. We do so by showing that every PCSP is
polynomial-time equivalent to a PCSP capturing systems of equations over
semigroups, a phenomenon observed for CSPs in [33].

Related work PCSPs are a qualitative approximation of CSPs; the goal is still
to satisfy all constraints, but in a weaker form. A recent related line of
work includes the series [7, 8, 9]. A traditional approach to approximation is
quantitative: maximising the number of satisfied constraints. Regarding
approximation of equations, Håstad showed that, for any Abelian group $G$ and
any $\varepsilon>0$, it is -hard to find a solution satisfying
$1/|G|+\varepsilon$ constraints [30] even if $1-\varepsilon$ constraints can
be satisfied. Hence, the random assignment, which satisfies $1/|G|$
constraints, is optimal! Håstad’s result has been extended to non-Abelian
groups in [24, 7]. Systems of equations have been studied, e.g., over
semigroups in [43], over monoids and semigroups in [33], and over arbitrary
finite algebras in [37, 35, 12, 39].

##  2 Preliminaries

We denote by $[k]$ the set $\\{1,2,\ldots,k\\}$. We write
$\operatorname{id}_{X}$ for the identity map on a set $X$. We use the
lowercase boldface font for tuples; e.g., we write $\bm{b}$ for a tuple
$(b_{1},\dots,b_{n})$.

Algebraic structures A _semigroup_ $S$ is a set equipped with an associative
binary operation, for which we use multiplicative notation. An element $s$ of
$S$ is _regular_ if $s^{2}t=s$ and $ts=st$ for some $t$ in $S$. Two elements
$a,b\in S$ commute if $ab=ba$. An _Abelian_ semigroup is a semigroup in which
every two elements commute. A _semigroup homomorphism_ from a semigroup
$S_{1}$ to a semigroup $S_{2}$ is a map $\varphi:S_{1}\to S_{2}$ satisfying
$\varphi(s\cdot_{S_{1}}t)=\varphi(s)\cdot_{S_{2}}\varphi(t)$.222I.e., the
multiplication on the LHS is in $S_{1}$, whereas the multiplication on the RHS
is in $S_{2}$. Given two elements $s,t\in S$ we write $s\sqsubseteq t$ if $s$
can be expressed as a product of elements in $S$ including $t$. Note that
$\sqsubseteq$ constitutes a partial order over any semigroup. We define the
equivalence relation $\sim$ by $s\sim t$ whenever $s\sqsubseteq t$ and
$t\sqsubseteq s$.

A _monoid_ is a semigroup containing an identity element for its binary
operation, denoted by $e$. A _monoid homomorphism_ from a monoid $M_{1}$ to a
monoid $M_{2}$ is a map $\varphi:M_{1}\to M_{2}$ satisfying
$\varphi(x\cdot_{M_{1}}y)=\varphi(x)\cdot_{M_{2}}\varphi(y)$ and
$\varphi(e_{M_{1}})=e_{M_{2}}$. We say that $\varphi$ is _Abelian_ if its
image $\operatorname{Im}(\phi)$ is an Abelian monoid. We say that a monoid
homomorphism $\psi$ from $M_{1}$ to $M_{2}$ _extends_ $\varphi$ if
${\left.\kern-1.2pt\psi\right|_{\mathrm{dom}(\varphi)}}=\varphi$.

A _group_ is a monoid in which each element has an inverse. A _group
homomorphism_ from a group $G_{1}$ to a group $G_{2}$ is a map
$\varphi:G_{1}\to G_{2}$ satisfying
$\varphi(x\cdot_{G_{1}}y)=\varphi(x)\cdot_{G_{2}}\varphi(y)$ (which implies
that also the inverses and the identity element are preserved).

Given a monoid $M$, a subset $G\subseteq M$ is called a _subgroup_ if $G$
equipped with $M$’s binary operation is a group, meaning that there is a
distinguished element $e_{G}\in G$ satisfying that (1)
$e_{G}\cdot_{M}g=g\cdot_{M}e_{G}=g$ for all $g\in G$, and (2) for each element
$g\in G$ there exists $h\in G$ satisfying $g\cdot_{M}h=h\cdot_{M}g=e_{G}$. We
say that $M$ is a _union of subgroups_ if every element $s\in M$ belongs to a
subgroup of $M$.

We use the standard product (and also the power) of a semigroup (monoid,
group), which is defined componentwise. We use the symbol $\preceq$ for a
substructure; e.g., if $S$ is a semigroup then we write $T\preceq S$ to
indicate that $T$ is a subsemigroup of $S$ (and similarly for monoids and
groups).

Relational structures A _relational signature_ $\sigma$ consists of a finite
set of relation symbols $R$, each with a finite arity
$\mathrm{ar}(R)\in\mathbb{N}$. A _relational structure_ ${\bm{A}}$ over the
signature $\sigma$, or a $\sigma$-structure, consists of a finite set $A$ and
a relation $R^{\bm{A}}\subseteq A^{k}$ of arity $k=\mathrm{ar}(R)$ for every
$R\in\sigma$. Let ${\bm{A}}$ and ${\bm{B}}$ be two $\sigma$-structures. A map
$h:A\to B$ is called a _homomorphism_ from ${\bm{A}}$ to ${\bm{B}}$ if $h$
preserves all relations in ${\bm{A}}$; i.e., if, for every $R\in\sigma$,
$h(\mathbf{x})\in R^{\bm{B}}$ whenever $\mathbf{x}\in R^{\bm{A}}$, where $h$
is applied componentwise. We denote the existence of a homomorphism from
${\bm{A}}$ to ${\bm{B}}$ by writing ${\bm{A}}\to{\bm{B}}$. A _template_ is a
pair $({\bm{A}},{\bm{B}})$ of relational structures such that
${\bm{A}}\to{\bm{B}}$.

A $k$-ary _polymorphism_ of a template $({\bm{A}},{\bm{B}})$ over signature
$\sigma$ is a map $p:A^{k}\to B$ that preserves all relations $R^{\bm{A}}$
from ${\bm{A}}$ in the following sense: For any $\mathrm{ar}(R)\times k$
matrix whose columns belong to $R^{\bm{A}}$, applying $p$ row-wise results in
a tuple that belongs to $R^{\bm{B}}$. We denote by
$\operatorname{Pol}({\bm{A}},{\bm{B}})$ the set of all polymorphisms of
$({\bm{A}},{\bm{B}})$.333Equivalently, $p$ is a polymorphism of
$({\bm{A}},{\bm{B}})$ if $p$ is a homomorphism from the $k$-th power of
${\bm{A}}$ to ${\bm{B}}$.

Minions A _minion_ $\mathscr{M}$ consists of a set $\mathscr{M}(n)$ for each
positive number $n$, and a map
$\pi^{\mathscr{M}}:\mathscr{M}(n)\rightarrow\mathscr{M}(m)$ for each map
$\pi:n\rightarrow m$ satisfying (1)
$\operatorname{id}_{[n]}^{\mathscr{M}}=\operatorname{id}_{\mathscr{M}(n)}$ for
every $n>0$, and (2)
$\pi^{\mathscr{M}}\circ\tau^{\mathscr{M}}=(\pi\circ\tau)^{\mathscr{M}}$ for
every pair of suitable maps $\pi,\tau$. When the minion is clear from the
context, we write $p^{(\pi)}$ for $\pi^{\mathscr{M}}(p)$. Elements
$p\in\mathscr{M}(n)$ are called $n$-ary, and whenever $p^{(\pi)}=q$ we say
that $q$ is a _minor_ of $p$. A _minion homomorphism_
$\xi:\mathscr{M}\to\mathscr{N}$ is a map from a minion $\mathscr{M}$ to
another minion $\mathscr{N}$ that preserves arities and minor operations.
I.e., $\xi(p^{(\pi)})=(\xi(p))^{(\pi)}$ for every minor $p^{(\pi)}$.

Given a template $({\bm{A}},{\bm{B}})$, its set of polymorphisms
$\operatorname{Pol}({\bm{A}},{\bm{B}})$ can be equipped with a minion
structure in a natural way. That is, $n$-ary elements of
$\operatorname{Pol}({\bm{A}},{\bm{B}})$ are just $n$-ary polymorphisms
$p:A^{n}\rightarrow B$. Additionally, given some $n$-ary polymorphism $p$, and
some map $\pi:[n]\rightarrow[m]$, the minor $p^{(\pi)}$ is the polymorphism
$q:A^{m}\rightarrow B$ given by $(a_{1},\dots,a_{m})\mapsto
p(b_{1},\dots,b_{n})$, where $b_{i}=a_{\pi(i)}$ for each $i\in[n]$.

Given a minion $\mathscr{M}$, we define two special types of elements. An
element $p\in\mathscr{M}(2k+1)$ is called _alternating_ if $p^{(\pi)}=p$ for
any permutation $\pi:[2m+1]\to[2m+1]$ that preserves parity, and
$p^{(\pi_{1})}=p^{(\pi_{2})}$, where for each $i=1,2$ the map $\pi_{i}$ is
given by $1\mapsto i$, $2\mapsto i$ and $j\mapsto j$ for all $j>2$. An element
$p\in\mathscr{M}(2k+1)$ is called _$2$ -block-symmetric_ if the set $[2k+1]$
can be partitioned into two blocks of size $k+1$ and $k$ in such a way that
$p^{(\pi)}=p$ for any map $\pi:[2m+1]\to[2m+1]$ that permutes elements within
each block.

Constraint satisfaction Let $({\bm{A}},{\bm{B}})$ be a template with common
signature $\sigma$. The _promise constraint satisfaction problem_ (PCSP) with
template $({\bm{A}},{\bm{B}})$ is the following computational problem, denoted
by $\operatorname{PCSP}({\bm{A}},{\bm{B}})$. Given a $\sigma$-structure
$\bm{X}$, output Yes if $\bm{X}\to{\bm{A}}$ and output No if
$\bm{X}\not\to{\bm{B}}$. This is the decision version. In the search version,
one is given a $\sigma$-structure $\bm{X}$ with the promise that
$\bm{X}\to{\bm{A}}$; the goal is to find a homomorphism from $\bm{X}$ to
${\bm{B}}$ (which necessarily exists, as $\bm{X}\to{\bm{A}}$ and
${\bm{A}}\to{\bm{B}}$, and homomorphisms compose). It is known that the
decision version polynomial-time reduces to the search version (but it is not
known whether the two variants are polynomial-time equivalent) [5]. In our
results, the positive (tractability) results are for the search version,
whereas the hardness (intractability) results are for the decision version. We
denote by $\operatorname{CSP}({\bm{A}})$ the problem
$\operatorname{PCSP}({\bm{A}},{\bm{A}})$; this is the standard (non-promise)
constraint satisfaction problem (CSP). For CSPs, the decision version and the
search version are polynomial-time equivalent [18].

We need two existing algorithms for PCSPs, namely the AIP algorithm [5] and
the strictly more powerful $\textsc{BLP}+\textsc{AIP}$ algorithm [16]. Their
power is captured by the following results.

######  Theorem 1 ([5]).

Let $({\bm{A}},{\bm{B}})$ be a template. Then
$\operatorname{PCSP}({\bm{A}},{\bm{B}})$ is solved by AIP if and only if
$\operatorname{Pol}({\bm{A}},{\bm{B}})$ contains alternating maps of all odd
arities.

######  Theorem 2 ([16]).

Let $({\bm{A}},{\bm{B}})$ be a template. Then
$\operatorname{PCSP}({\bm{A}},{\bm{B}})$ is solved by
$\textsc{BLP}+\textsc{AIP}$ if and only if
$\operatorname{Pol}({\bm{A}},{\bm{B}})$ contains $2$-block-symmetric maps of
all odd arities.

##  3 Overview of Results

Promise equations over monoids and groups Our first and main result is a
dichotomy theorem for solving promise equations over monoids and thus also, as
a special case, over groups. We first define equations in the standard, non-
promise setting as it is be useful for mentioning previous work and for our
own proofs.

An _equation_ over a semigroup $S$ is an expression of the form $x_{1}\dots
x_{n}=y_{1}\dots y_{m}$, where each $x_{i},y_{i}$ is either a variable or some
element from $S$, referred to as a _constant_. A _system of equations_ over
$S$ is just a set of equations. A solution to such a system is an assignment
of elements of $S$ to the variables of the system that makes all equations
hold. Equations and systems of equations are defined similarly for monoids and
groups. The only difference is that for groups we allow “inverted variables”
$x^{-1}$ in the equations, which are interpreted as inverses of the elements
assigned to $x$.

In the context of CSPs, it is common to consider only restricted “types” of
equations that can then express all other equations. The following definition
captures systems of equations where each equation is either of the form
$x_{1}x_{2}=x_{3}$, for three variables, or $x=c$, fixing a variable to a
constant. It is well known that restricting to systems of equations of this
kind is without loss of generality, cf. Appendix A.

######  Definition 1.

Let $S$ be a semigroup and $T\preceq S$ a subsemigroup. The relational
structure $\operatorname{Eqn}(S,T)$ has universe $S$, and the following
relations:

  * •

A ternary relation $R_{\times}=\\{(s_{1},s_{2},s_{3})\in S^{3}\mid
s_{1}s_{2}=s_{3}\\}$, and

  * •

a singleton unary relation $R_{t}={t}$ for each $t\in T$.

This template captures systems of equations of the kind described above when
we allow only constants in a subsemigroup $T$ of the ambient semigroup $S$.
Similarly, we define the templates $\operatorname{Eqn}(M,N)$,
$\operatorname{Eqn}(G,H)$ in the same way when $M$ is a monoid and $N\preceq
M$ a submonoid, and when $G$ is a group and $H\preceq G$ is a subgroup.
Observe that the definition of subgroup is more restrictive than the one of
submonoid and this in turn is more restrictive than the notion of
subsemigroup. We abuse the notation and write $\operatorname{Eqn}(S,T)$ for
$\operatorname{CSP}(\operatorname{Eqn}(S,T))$.

Previous works focused on problems $\operatorname{Eqn}(G,G)$ and
$\operatorname{Eqn}(M,M)$. Given a group $G$, it is known that
$\operatorname{Eqn}(G,G)$ is solvable in polynomial time (by AIP) if $G$ is
Abelian, and -hard otherwise [28]. Similarly, when $M$ is a monoid,
$\operatorname{Eqn}(M,M)$ is solvable in polynomial time if $M$ is Abelian and
it is the union of its subgroups, and -hard otherwise [33].

We now define promise equations.

######  Definition 2.

Let $S_{1},S_{2}$ be semigroups, and let $\varphi$ be a semigroup homomorphism
with $\mathrm{dom}(\varphi)\preceq S_{1}$ and
$\operatorname{Im}(\varphi)\preceq S_{2}$. The _promise system of equations
over semigroups_ problem $\operatorname{PEqn}(S_{1},S_{2},\varphi)$ is the
$\operatorname{PCSP}({\bm{A}},{\bm{B}})$, where $A=S_{1}$, $B=S_{2}$, and the
relations are defined as follows:

  * •

A ternary relation $R_{\times}^{\bm{A}}=\\{(s_{1},s_{2},s_{3})\in
S_{1}^{3}\mid s_{1}s_{2}=s_{3}\\}$, and
$R_{\times}^{\bm{B}}=\\{(s_{1},s_{2},s_{3})\in S_{2}^{3}\mid
s_{1}s_{2}=s_{3}\\}$.

  * •

For each $t\in\mathrm{dom}(\varphi)$, a unary relation given by
$R^{\bm{A}}_{t}=\\{t\\}$, and $R^{\bm{B}}_{t}=\\{\varphi(t)\\}$.

For this template to be well defined there should be a homomorphism from
${\bm{A}}$ to ${\bm{B}}$, which is equivalent to the existence of a semigroup
homomorphism $\psi:S_{1}\rightarrow S_{2}$ that extends $\varphi$.

Analogously, we also define the _promise system of equations over monoids_
problem and the _promise system of equations over groups_ problem by replacing
semigroup-related notions with monoid-related notions and group-related
notions respectively. Observe that the problem $\operatorname{Eqn}(S,T)$
described before corresponds precisely to
$\operatorname{PEqn}(S,S,\operatorname{id}_{T})$.

We can now state our main result.

######  Theorem 3 (Main).

$\operatorname{PEqn}(M_{1},M_{2},\varphi)$ is solvable in polynomial time by
$\textsc{BLP}+\textsc{AIP}$ if there is an Abelian homomorphism
$\psi:M_{1}\rightarrow M_{2}$ extending $\varphi$ and
$\operatorname{Im}(\psi)$ is a union of subgroups. Otherwise,
$\operatorname{PEqn}(M_{1},M_{2},\varphi)$ is -hard.

For the special case of groups, we get a simpler tractability criterion and a
simpler algorithm.

######  Corollary 1.

$\operatorname{PEqn}(G_{1},G_{2},\varphi)$ is solvable in polynomial time via
AIP if there is an Abelian homomorphism $\psi:G_{1}\rightarrow G_{2}$
extending $\varphi$. Otherwise, $\operatorname{PEqn}(G_{1},G_{2},\varphi)$ is
-hard.

As easy corollaries, Theorem 3 applies in the special case of non-promise
setting.

######  Corollary 2.

Given two monoids $N\preceq M$, $\operatorname{Eqn}(M,N)$ is solvable in
polynomial time by $\textsc{BLP}+\textsc{AIP}$ if there is an Abelian
endomorphism of $M$ extending $\operatorname{id}_{N}$ whose image is a union
of subgroups, and is -hard otherwise.

######  Corollary 3.

Given two groups $H\preceq G$, $\operatorname{Eqn}(G,H)$ is solvable in
polynomial time by AIP if there is an Abelian endomorphism of $G$ that extends
$\operatorname{id}_{H}$, and is -hard otherwise.

######  Example 1.

Let $G$ be the dihedral group on four elements, and $H$ be the symmetric group
on four elements. Observe that $G$ can be seen as a subgroup of $H$ in a
natural way: $H$ consists of all permutations on four elements, while $G$
contains only those that are symmetries of the square. The group $G$ is
generated by the right $90$-degree rotation $r$ and an arbitrary reflection
$f$ that leaves no element fixed. We consider two group homomorphisms
$\varphi_{1},\varphi_{2}$ with $\mathrm{dom}(\varphi_{i})\preceq G$ and
$\operatorname{Im}(\varphi_{i})\preceq H$. The domain of both homomorphism is
the subgroup $\\{e,r,r^{2},r^{3}\\}\preceq G$. Then, $\varphi_{1}$ is given by
$r\mapsto r^{2}$, and $\varphi_{2}$ is given by $r\mapsto r$. The following
hold:

  * •

$\operatorname{PEqn}(G,H,\varphi_{1})$ is tractable, and solvable via AIP.
However both $\operatorname{Eqn}(G,$ $\mathrm{dom}(\varphi_{1}))$ and
$\operatorname{Eqn}(H,\operatorname{Im}(\varphi_{1}))$ are NP-hard.

  * •

$\operatorname{PEqn}(G,H,\varphi_{2})$ is NP-hard.

To see the first item, observe that the group homomorphism $\psi:G\rightarrow
H$ given by $r\mapsto r^{2}$ and $f\mapsto f$ is Abelian (its image is
isomorphic to the direct product $Z_{2}\times Z_{2}$) and extends
$\varphi_{1}$. Hardness of $\operatorname{Eqn}(G,\mathrm{dom}(\varphi_{1}))$
is a consequence of the fact that the commutator subgroup of $G$ is
$\\{e,r,r^{2},r^{3}\\}\succeq\mathrm{dom}(\varphi_{1})$, so
$\mathrm{dom}(\varphi_{1})$ is included in the kernel of any Abelian
endomorphism of $G$. Similarly, hardness of
$\operatorname{Eqn}(H,\operatorname{Im}(\varphi_{1}))$ follows from the fact
that the commutator subgroup of $H$ is the alternating group on four elements,
and has $\operatorname{Im}(\varphi_{1})$ as a subgroup.

The second item can be proved by observing that the only normal subgroup of
$G$ that does not intersect $\mathrm{dom}(\varphi_{2})$ is the trivial
subgroup, so any homomorphism $\psi:G\rightarrow H$ that extends $\varphi_{2}$
needs to be injective, and thus non-Abelian.

We say that $\operatorname{PCSP}({\bm{A}},{\bm{B}})$ is _finitely tractable_
if there is ${\bm{C}}$ such that ${\bm{A}}\to{\bm{C}}\to{\bm{B}}$ and
$\operatorname{CSP}({\bm{C}})$ is solvable in polynomial time. The tractable
cases in Theorem 3 are in fact finitely tractable; for details, cf. Lemma 8 in
Appendix B.

The power of $\textsc{BLP}+\textsc{AIP}$ is necessary in Theorem 3 in the
sense that AIP does not suffice for all monoids, even for (non-promise) CSPs,
unlike in the case of groups. Indeed, adding a fresh element to a group that
serves as the monoid identity fools AIP; for details, cf. Lemma 9 in Appendix
B.

Promise equations over semigroups As our next result, we prove that every PCSP
is polynomial-time equivalent to a problem of the form
$\operatorname{PEqn}(S_{1},S_{2},\varphi)$ over some semigroups $S_{1},S_{2}$.
Hence, extending our classification of promise equations beyond monoids is
difficult in the sense that understanding the computational complexity of
promise equations over semigroups is as hard as classifying all PCSPs. This
result is analogous to the one known in the non-promise setting obtained in
[33], whose proof we closely follow. One difficulty in lifting the result from
[33] is the lack of constants in the promise setting. The details can be found
in Section 6.

######  Theorem 4.

Let $({\bm{A}},{\bm{B}})$ be a template. Then there are semigroups
$S_{1},S_{2}$ and a semigroup homomorphism $\varphi$ with
$\mathrm{dom}(\varphi)\preceq S_{1}$ and $\operatorname{Im}(\varphi)\preceq
S_{2}$ such that $\operatorname{PCSP}({\bm{A}},{\bm{B}})$ is polynomial-time
equivalent to $\operatorname{PEqn}(S_{1},S_{2},\varphi)$.

Monoidal minions As our third result, we investigate minions based on monoids.
For PCSPs whose polymorphism minions are homomorphically equivalent to such
minions, we establish a dichotomy. This is a building block in the proof of
our main result, but may be interesting in its own right. In this direction,
we show that for each monoidal minion $\mathscr{M}$, there are PCSP templates
whose polymorphism minions are isomorphic to $\mathscr{M}$. For a finite set
$I$, a tuple $(a_{i})_{i\in[n]}\in M^{n}$ is called commutative if each pair
of its elements commute.

######  Definition 3.

Given an element $a\in M$ the _monoidal minion_ $\mathscr{M}_{M,a}$ is the one
where for each $n\in\mathbb{N}$ the elements $\bm{b}\in\mathscr{M}_{M,a}(n)$
consist of commutative tuples $\bm{b}\in M^{n}$ with $\prod_{i\in[n]}b_{i}=a$,
and where for each $m>0$ and each $\pi:[n]\rightarrow[m]$ the minor
$\bm{b}^{(\pi)}$ is the tuple $\bm{c}\in M^{m}$ given by
$c_{j}=\prod_{i\in\pi^{-1}(j)}b_{i}$, and the empty product equals the
identity element $e$.

######  Theorem 5.

Let $M$ be a finite monoid and let $a\in M$. Consider a template
$({\bm{A}},{\bm{B}})$ with $\operatorname{Pol}({\bm{A}},{\bm{B}})$
homomorphically equivalent to $\mathscr{M}_{M,a}$. If $a$ is regular in $M$
then $\operatorname{PCSP}({\bm{A}},{\bm{B}})$ is solvable in polynomial time
by $\textsc{BLP}+\textsc{AIP}$. Otherwise,
$\operatorname{PCSP}({\bm{A}},{\bm{B}})$ is -complete.

Next, we show that there are templates whose polymorphism minions are of the
considered type (up to isomorphism).

######  Theorem 6.

Let $M$ be a monoid, and $a\in M$ an arbitrary element. Then the template
$({\bm{A}},{\bm{B}})$ described below satisfies that
$\operatorname{Pol}({\bm{A}},{\bm{B}})\simeq\mathscr{M}_{M,a}$.444We use
$\simeq$ to denote the isomorphism relation, i.e., the existence of a
bijection between the minions that preserves arities and minor operations. The
signature $\sigma$ of ${\bm{A}}$ and ${\bm{B}}$ contains three relation
symbols: a ternary symbol $R$, and two unary ones $C_{0},C_{1}$. We define
$A=\\{0,1\\}$, $R^{\bm{A}}=\\{(1,0,0),(0,1,0),(0,0,1)\\}$,
$C_{0}^{\bm{A}}=\\{0\\}$ and $C_{1}^{\bm{A}}=\\{1\\}$. The universe $B$ of
${\bm{B}}$ is $\mathscr{M}_{M,a}(2)$. We define $R^{\bm{B}}$ as the set of
triples in $\left(\mathscr{M}_{M,a}(2)\right)^{3}$ of the form
$((c_{1},c_{2}c_{3}),(c_{2},c_{1}c_{3}),(c_{3},c_{1}c_{2}))$, where
$c_{1},c_{2},c_{3}\in M$ commute pairwise, and $c_{1}c_{2}c_{3}=a$. Finally,
the unary relations $C_{0}^{\bm{B}}$ and $C_{1}^{\bm{B}}$ are the singleton
sets containing the tuples $(e,a)$ and $(a,e)$ respectively.555The map
$f:A\rightarrow B$ given by $0\mapsto(e,a)$ and $1\mapsto(a,e)$ is a
homomorphism from ${\bm{A}}$ to ${\bm{B}}$. The structure ${\bm{A}}$
corresponds to the “$1$-in-$3$” template, where both constants are added, and
${\bm{B}}$ is the so-called “free structure” [5] of $\mathscr{M}_{M,a}$
generated by ${\bm{A}}$.

Finally, we remark that monoidal minions are natural objects of study, as they
include other relevant previously studied minions.

######  Remark 1.

Consider the Abelian monoid $M=\\{0,1,\epsilon\\}$, whose multiplicative
identity is $0$, and where $1\cdot
1=1\cdot\epsilon=\epsilon\cdot\epsilon=\epsilon$. The elements of
$\mathcal{M}_{M,1}$ are tuples with all zero entries except for a single $1$
entry. Hence $\mathcal{M}_{M,1}$, corresponds to the so-called trivial minion
$\mathscr{T}$ consisting of all projections (also known as dictators) on a
two-element set. This minion represents the hardness boundary for CSPs, in the
sense that a CSP is NP-hard if and only if its polymorphism minion maps
homomorphically to $\mathscr{T}$ [18, 44].

If we allow infinite monoids to be considered, then monoidal minions include
important minions that capture solvability via relevant algorithms. Consider
the monoid $M=\\{(r,z)\in\mathbb{Q}\times\mathbb{Z}\mid r\in[0,1],\text{ and
}r=0\text{ implies }z=0\\}$, where the binary operation is given by
coordinate-wise addition, and the identity is $(0,0)$. Then
$\mathscr{M}_{M,(1,1)}$ is precisely the minion
$\mathscr{M}_{\textsc{BLP}+\textsc{AIP}}$ described in [16], which expresses
the power of $\textsc{BLP}+\textsc{AIP}$. Similarly, the minions described in
[5] to capture the power of BLP and AIP are monoidal minions as well.

##  4 Monoidal Minions: Proof of Theorem 5

Tractability We use the characterisation of the power of
$\textsc{BLP}+\textsc{AIP}$ from Theorem 2 for the tractability part of
Theorem 5. Observe that if there is a minion homomorphism
$\xi:\mathscr{M}_{M,a}\rightarrow\operatorname{Pol}({\bm{A}},{\bm{B}})$ and
$p\in\mathscr{M}_{M,a}$ is a $(2k+1)$-ary $2$-block-symmetric element, then so
is $\xi(p)$. Hence, showing that $\mathscr{M}_{M,a}$ has $2$-block-symmetric
elements of all arities proves that $\operatorname{PCSP}({\bm{A}},{\bm{B}})$
is solvable in polynomial time via $\textsc{BLP}+\textsc{AIP}$. For each $k>0$
consider the $(2k+1)$-ary element of $\mathscr{M}_{M,a}$ that is $k+1$
consecutive $a$’s followed by $k$ consecutive $b$’s. To see that this this is
indeed an element of $\mathscr{M}_{M,a}$ we need to check that
$a^{k+1}b^{k}=a$. This follows from the assumption that $a$ is regular and
using $a^{k+1}b^{k}=a(ba)^{k}$. This tuple is $2$-block-symmetric, with the
blocks corresponding to $a$ and $b$ (of sizes $k$ and $k+1$, respectively).

Intractability We prove the intractability part of Theorem 5 (as well as other
hardness results later in this paper) using the following result.

######  Theorem 7 ([5]).

Let $\mathscr{M}=\operatorname{Pol}({\bm{A}},{\bm{B}})$, and let $K,L>0$ be
any fixed integers. Suppose that $M$ satisfies the following condition:

$\mathscr{M}=\bigcup_{\ell\in[L]}\mathscr{M}_{\ell}$, and for each
$\ell\in[L]$ there is a map $p\mapsto\mathcal{I}_{\ell}(p)$ that sends each
$p\in\mathscr{M}_{\ell}$ to a set of its coordinates $\mathcal{I}_{\ell}(p)$
of size at most $K$. Furthermore, suppose that for each $\ell\in[L]$ and for
each minor $p^{(\pi)}=q$ where $p,q\in\mathscr{M}_{\ell}$ it holds that
$\pi(\mathcal{I}_{\ell}(p))\bigcap\mathcal{I}_{\ell}(q)\neq\emptyset$.

Then $\operatorname{PCSP}({\bm{A}},{\bm{B}})$ is -complete.

Given a template $({\bm{A}},{\bm{B}})$, if there is a minion homomorphism
$\xi:\operatorname{Pol}({\bm{A}},{\bm{B}})\rightarrow\mathscr{M}_{M,a}$ and
$\mathscr{M}_{M,a}$ satisfies the condition in the previous theorem, so does
$\operatorname{Pol}({\bm{A}},{\bm{B}})$. Indeed, if
$\mathscr{M}_{M,a}=\bigcup_{\ell\in[L]}\mathscr{M}_{\ell}$, then we can write
$\operatorname{Pol}({\bm{A}},{\bm{B}})=\bigcup_{\ell\in[L]}\xi^{-1}(\mathscr{M}_{\ell})$.
Additionally, if the map $\mathcal{I}_{\ell}$ witnesses the condition in the
theorem for $\mathscr{M}_{\ell}$, then the map $\mathcal{I}^{\prime}_{\ell}$
given by $p\mapsto\mathcal{I}_{\ell}(\xi(p))$ witnesses the same condition for
$\xi^{-1}(\mathscr{M}_{\ell})$. Hence, we show the hardness part of Theorem 5
by proving that $\mathscr{M}_{M,a}$ satisfies the assumptions in Theorem 7
when $a\in M$ is not regular.

Given a monoid $M$, we write $a\sqsubseteq^{\operatorname{A}}b$ for $a,b\in M$
if there is a third element $c\in M$ that commutes with $b$ such that $bc=a$.
We put $a\sim^{\operatorname{A}}b$ when both
$a\sqsubseteq^{\operatorname{A}}b$ and $b\sqsubseteq^{\operatorname{A}}a$
hold, and $a\sqsubsetneq^{\operatorname{A}}$ when
$a\sqsubseteq^{\operatorname{A}}b$ holds but
$b\sqsubseteq^{\operatorname{A}}a$ does not. Note that
$\sqsubseteq^{\operatorname{A}}$ is a preorder on $M$. We use the following
simple observation.

######  Observation 1.

Let $M$ be a monoid and $a,b,c\in M$ be three elements that commute pairwise.
Suppose that $abc\sqsubsetneq^{\operatorname{A}}ab$. Then
$ac\sqsubsetneq^{\operatorname{A}}a$.

###### Proof.

We prove the contrapositive. Suppose that $a\sqsubseteq^{\operatorname{A}}ac$.
That is, there is some $d\in M$ that commutes with $ac$ and satisfies $acd=a$.
We have $dabc=(dac)b=(acd)b=ab$ $abcd=c(abd)=ca=ac$, and thus $dabc=abcd=ab$,
proving that $abc\sqsupseteq^{\operatorname{A}}ab$. ∎

Assume that $a$ is not regular. That is, that $a^{2}b\neq a$ for every $b\in
M$ that commutes with $a$. Let $\bm{b}\in\mathscr{M}_{M,a}(n)$ for some number
$n>0$. A coordinate $j\in[n]$ is called _relevant_ in $\bm{b}$ if
$\prod_{i\in[m]\setminus
j}b_{i}\sqsupsetneq^{\operatorname{A}}\prod_{i\in[n]}b_{i}$. Consider the map
$\mathcal{I}$ that assigns to each $\bm{b}\in\mathscr{M}_{M,a}$ its set of
relevant coordinates. Claims 1 through 3 proved below establish the required
assumptions in Theorem 7 with $L=1$ and $K=|m|$, thus showing -hardness of
$\operatorname{PCSP}({\bm{A}},{\bm{B}})$.

Claim 1: $\bm{b}$ has at most $|M|$ relevant coordinates.

Let $\\{i_{1},\dots,i_{h}\\}\subseteq[n]$ be the set of relevant coordinates
of $\bm{b}$. Given $k\in[h]$ we define

$c_{k}=\prod_{j\in[k-1]}b_{i_{j}},\quad\text{and}\quad
d_{k}=\prod_{j\in[n]\setminus\\{i_{1},\dots,i_{k}\\}}b_{j}.$

The following hold: (1) $a=d_{k}c_{k}b_{i_{k}}$, (2) $b_{i_{k}},c_{k}$ and
$d_{k}$ commute pairwise, and (3) as $i_{k}$ is a relevant coordinate, it
holds that $d_{k}c_{k}b_{i_{k}}\sqsubsetneq^{\operatorname{A}}d_{k}c_{k}$.
Applying 1, we obtain that
$c_{k}b_{i_{k}}\sqsubsetneq^{\operatorname{A}}c_{k}$. Expanding the definition
of $c_{k}$ this means that

$\prod_{j\in[k]}b_{i_{j}}\sqsubsetneq^{\operatorname{A}}\prod_{j\in[k-1]}b_{i_{j}}.$

This holds for all $k\in[h]$, so in particular the products
$\prod_{j\in[k]}b_{i_{j}}$ must be pairwise different and the number $h$ of
relevant coordinates is at most $|M|$, proving the claim.

Claim 2: Minors preserve relevant coordinates.

Let $\bm{c}=\bm{b}^{(\pi)}$, where $\pi:[n]\rightarrow[m]$ is a map and let
$i\in[n]$ be a relevant coordinate of $\bm{b}$. We want to show that
$j=\pi(i)$ is a relevant coordinate of $\bm{c}$. Indeed, if that was not the
case we would have that

$\prod_{k\in[n]\setminus\pi^{-1}(j)}b_{k}\sqsubseteq^{\operatorname{A}}a.$

However, $i\in\pi^{-1}(j)$, so we know that
$\prod_{k\in[n]\setminus\\{i\\}}b_{k}\sqsubseteq^{\operatorname{A}}\prod_{k\in[n]\setminus\pi^{-1}(j)}b_{k}$.
Putting this together with the previous identity shows that

$\prod_{k\in[n]\setminus\pi^{-1}(j)}b_{k}\sqsubseteq^{\operatorname{A}}a,$

contradicting the fact that $i$ was a relevant coordinate of $\bm{b}$.

Claim 3: $\bm{b}$ has at least one relevant coordinate.

Suppose otherwise for the sake of contradiction. Then for each $i\in[n]$ there
is an element $c_{i}\in M$ that commutes with $a$ such that
$ac_{i}=\prod_{i\in[n]\setminus\\{j\\}}b_{i}$. Let $c=\prod_{i\in[n]}c_{i}$.
Observe that $c$ itself commutes with $a$. However, one can check that that
$a^{2}c=a$, contradicting our assumption that $a$ was not regular. Indeed,

$\displaystyle a^{2}c$
$\displaystyle=\left(\prod_{i=1}^{n}b_{i}\right)\left(ac_{1}\right)\left(\prod_{i=2}^{n}c_{i}\right)=\left(\prod_{i=1}^{n}b_{i}\right)\left(\prod_{i\in[n]\setminus\\{1\\}}b_{i}\right)\left(\prod_{i=2}^{n}c_{i}\right)$
$\displaystyle=\left(\prod_{i=2}^{n}b_{i}\right)\left(ac_{2}\right)\left(\prod_{i=3}^{n}c_{i}\right)=\left(\prod_{i=2}^{n}b_{i}\right)\left(\prod_{i\in[n]\setminus\\{2\\}}b_{i}\right)\left(\prod_{i=3}^{n}c_{i}\right)$
$\displaystyle=\left(\prod_{i=3}^{n}b_{i}\right)\left(ac_{3}\right)\left(\prod_{i=4}^{n}c_{i}\right)=\left(\prod_{i=3}^{n}b_{i}\right)\left(\prod_{i\in[n]\setminus\\{3\\}}b_{i}\right)\left(\prod_{i=4}^{n}c_{i}\right)$
$\displaystyle=\dots=\left(\prod_{i=n}^{n}b_{i}\right)\left(\prod_{i\in[n]\setminus\\{n\\}}b_{i}\right)=a.$

##  5 Equations Over Monoids and Groups: Proofs of Theorem 3 and Corollary 1

We need a simple characterisation of the polymorphisms of promise equation
templates, and various characterisations of regularity; both are proved in
Appendix C.

######  Lemma 1.

Consider a template $\operatorname{PEqn}(Z_{1},Z_{2},\varphi)$ of promise
equations over semigroups/monoids/groups. A map $p:Z_{1}^{n}\rightarrow Z_{2}$
is a polymorphism of $\operatorname{PEqn}(Z_{1},Z_{2},\varphi)$ if and only if
$p$ is a semigroup/monoid/group homomorphism and $p(s,s,\dots,s)=\varphi(s)$
for all $s\in\mathrm{dom}(\varphi)$.

######  Lemma 2.

Let $M$ be a monoid and $s\in M$. Then the following are equivalent:

  1. 1.

$s$ is regular,

  2. 2.

$s^{k}=s$ for some $k>1$,

  3. 3.

$s$ belongs to a subgroup of $M$,

  4. 4.

$s\sqsubseteq s^{2}$.

With these two lemmas, we can now prove our main result.

See 3

###### Proof.

We prove both implications. Suppose that such homomorphism $\psi$ exists. As
$\operatorname{Im}(\psi)$ is a union of subgroups, by Lemma 2 there is some
number $k>1$ such that $s^{k}=s$ for all $s\in\operatorname{Im}(\psi)$. Let
$n>0$ be arbitrary. Consider the map $p:M_{1}^{2n+1}\rightarrow M_{2}$ given
by

$(s_{i})_{i\in[2n+1]}\mapsto\left(\prod_{i\in[n+1]}\psi(s_{i})\right)\left(\prod_{i\in[n]}\psi(s_{i+n+1})^{k-2}\right),$

where the convention is that the zero-th power of an element equals the
identity of the monoid. We claim that $p$ is a $2$-block-symmetric
polymorphism of $\operatorname{PEqn}(M_{1},M_{2},\varphi)$ with the first
block consisting of the first $n+1$ coordinates, and the second block
consisting of the rest. The fact that $p$ is a $2$-block-symmetric map with
the blocks as claimed follows from the fact that $\psi$ is Abelian. To
complete the argument, we show that $p$ is a polymorphism of
$\operatorname{PEqn}(M_{1},M_{2},\varphi)$ using the characterisation from
Lemma 1. First, observe that the fact that $\psi$ is Abelian implies that $p$
is a monoid homomorphism. Indeed,

$\displaystyle p(s_{1},\dots,s_{2n+1})$ $\displaystyle
p(t_{1},\dots,t_{2n+1})$
$\displaystyle=\left(\prod_{i\in[n+1]}\psi(s_{i})\psi(t_{i})\right)\left(\prod_{i\in[n]}\psi(s_{i+n+1})^{k-1}\psi(t_{i+n+1})^{k-1}\right)$
$\displaystyle=p(s_{1}t_{1},\dots,s_{2n+1}t_{2n+1}),$

so $p$ preserves products. Now we only need to prove that
$p(s,\dots,s)=\varphi(s)$ for all $s\in\mathrm{dom}(\varphi)$ in order to show
that $p$ is a polymorphism. To see that this holds, observe that

$p(s,\dots,s)=\psi(s)^{n(k-1)+1}=\psi(s)=\varphi(s),$

where the last equality uses the fact that $\psi$ extends $\varphi$. This
completes the proof of the first implication via Theorem 2.

In the other direction, we show that
$\operatorname{PEqn}(M_{1},M_{2},\varphi)$ is -hard assuming there is no
Abelian homomorphism $\psi:M_{1}\rightarrow M_{2}$ extending $\varphi$ whose
image is a union of subgroups. Let $\mathscr{M}$ be the polymorphism minion of
$\operatorname{PEqn}(M_{1},M_{2},\varphi)$. Given a polymorphism
$p\in\mathscr{M}$, we define $\mathcal{N}(p)$ as the submonoid
$\\{p(s,\dots,s)\mid s\in M_{1}\\}\preceq M_{2}$. Observe that by assumption,
for a given polymorphism $p$ it holds that either the monoid $\mathcal{N}(p)$
is non-Abelian or that $\mathcal{N}(p)$ is not a union of subgroups. Define
$\Omega$ as the set of monoid homomorphisms $\psi:M_{1}\rightarrow M_{2}$ for
which $\operatorname{Im}(\psi)$ is not a union of subgroups. By Lemma 2, this
happens precisely when $\operatorname{Im}(\psi)$ contains some non-regular
element $a\in M_{2}$. Let $L=|\Omega|+1$, and let $K=\max(|M_{2}|,|\\{N\preceq
M_{2}\mid N\text{ is non-Abelian }\\}|$. We use Theorem 7 with the constants
$L,K$ to show -hardness. We define the following subminions of $\mathscr{M}$.

$\mathscr{M}_{\operatorname{A}}=\\{p\in\mathscr{M},\mid\mathcal{N}(p)\text{ is
not Abelian}\\},$

and given any monoid homomorphism $\psi\in\Omega$ we set

$\mathscr{M}_{\psi}=\\{p\in\mathscr{M},\mid p(s,\dots,s)=\psi(s)\text{ for all
}s\in M_{1}\\}.$

By the previous observation it holds that

$\mathscr{M}=\mathscr{M}_{\operatorname{A}}\bigcup_{\psi\in\Omega}\mathscr{M}_{\psi}.$

We give selection functions $\mathcal{I}$ for each of these sub-minions
satisfying the assumptions of Theorem 7. Suppose that
$\mathscr{M}_{\operatorname{A}}$ is not empty. Otherwise we are done defining
$\mathcal{I}_{\operatorname{A}}$. Let $p$ be any $n$-ary polymorphism in
$\mathscr{M}_{\operatorname{A}}$. Given $i\in[n]$ we define
$\mathcal{N}(p,i)\preceq M_{2}$ as the submonoid

$\\{p(s_{1},\dots,s_{n})\mid s_{i}\in M_{1},\text{ and }s_{j}=e\text{ when
$j\neq i$}\\}.$

We give some facts about these submonoids.

Fact 1:

The map $\phi:\prod_{i\in[n]}\mathcal{N}(p,i)\rightarrow M_{2}$ given by
$(s_{1},\dots s_{n})\mapsto\prod_{i\in[n]}s_{i}$ is a monoid homomorphism. In
particular, given $1\leq i<j\leq n$, any two elements
$t_{1}\in\mathcal{N}(p,i)$, $t_{2}\in\mathcal{N}(p,j)$ commute.

Fact 2:

If $\mathcal{N}(p,i)=\mathcal{N}(p,j)$ for some $i\neq j\in[n]$ then
$\mathcal{N}(p,i)$ is Abelian.

Fact 3:

The submonoid $\mathcal{N}(p)$ is contained in $\operatorname{Im}(\phi)$,
where $\phi$ is as defined in Fact 1. In particular, given that
$\mathcal{N}(p)$ is not Abelian, some $\mathcal{N}(p,i)$ must be non-Abelian.

Given an $n$-ary polymorphism $p\in\mathscr{M}_{\operatorname{A}}$, we define
$\mathcal{I}_{\operatorname{A}}(p)\subseteq[n]$ as the set of coordinates $i$
for which $\mathcal{N}(p,i)$ is non-Abelian. We claim that
$\mathcal{I}_{\operatorname{A}}$ satisfies the assumptions of Theorem 7.
Indeed, given some $n$-ary $p$:

  * •

$\mathcal{I}_{\operatorname{A}}(p)$ is non empty by Fact 3.

  * •

$|\mathcal{I}_{\operatorname{A}}(p)|\leq K$. Otherwise it would be that
$\mathcal{N}(p,i)=\mathcal{N}(p,j)$ for some different
$i,j\in\mathcal{I}_{\operatorname{A}}(p)$, contradicting the fact that
$\mathcal{N}(p,i)$ is non-Abelian (by Fact 2).

  * •

Suppose that $p=q^{(\pi)}$ for some $m$-ary $q$ and some
$\pi:[m]\rightarrow[n]$. Let $i\in\mathcal{I}_{\operatorname{A}}(p)$, then

$\mathcal{N}(p,i)\subseteq\left\\{\prod_{j\in\pi^{-1}(i)}s_{j}\mid
s_{j}\in\mathcal{N}(s,j)\text{ for all $j\in\pi^{-1}(i)$}\right\\}.$

As $\mathcal{N}(p,i)$ is non-Abelian, some submonoid $\mathcal{N}(q,j)$ with
$j\in\pi^{-1}(i)$ must be non-Abelian as well. This means that
$\mathcal{I}_{\operatorname{A}}(p)\subseteq\pi(\mathcal{I}_{\operatorname{A}}(q))$.

Now consider an arbitrary homomorphism $\psi\in\Omega$ for which
$\mathscr{M}_{\psi}$ is non-empty. We define a selection function
$\mathcal{I}_{\psi}$ satisfying the assumptions of Theorem 7. Let
$t\in\operatorname{Im}(\psi)$ be a non-regular element, and let $s\in M_{1}$
be such that $\psi(s)=t$. Let $\mathscr{M}_{M_{2},t}$ be the monoidal minion
defined in Definition 3. Consider the map
$\xi:\mathscr{M}_{\psi}\rightarrow\mathscr{M}_{M_{2},a}$ that sends any
$n$-ary polymorphism $p\in\mathscr{M}_{\psi}$ to the tuple
$(r_{1},\dots,r_{n})\in\mathscr{M}_{M_{2},a}(n)$ where for each $i\in[n]$

$r_{i}=p(s_{1},\dots,s_{n}),\quad\text{ where }s_{i}=s,\text{ and
}s_{j}=e\text{ for all $j\neq i$ }.$

Observe that this is a well-defined minion homomorphism from
$\mathscr{M}_{\psi}$ to $\mathscr{M}_{M_{2},t}$. Indeed, first observe that
$(r_{1},\dots,r_{n})$ belongs to the second minion. This holds because
$r_{1}r_{2}\dots r_{n}=p(s,\dots,s)=\psi(s)=t$, and for each $i\in[n]$ the
element $r_{i}$ belongs to $\mathcal{N}(p,i)$, so the $r_{i}$’s commute
pairwise by Fact 1 above. One can also check that $\xi$ preserves minors.

From the proof of Theorem 5 there is some selection function $\mathcal{I}$ on
$\mathscr{M}_{M_{2},t}$ satisfying the hypotheses of Theorem 7 for some
constant $K^{\prime}=|M_{2}|\leq K$ and $L=1$. Thus, we can define
$\mathcal{I}_{\psi}$ on $\mathscr{M}_{\psi}$ simply by setting
$\mathcal{I}_{\psi}(p)=\mathcal{I}(\xi(p))$ for each polymorphism
$p\in\mathscr{M}_{\psi}$.

Hence, have defined selection functions $\mathcal{I}_{\operatorname{A}}$ and
$\mathcal{I}_{\psi}$ for each $\psi\in\Omega$ that satisfy the requirements of
Theorem 7, showing that $\operatorname{PEqn}(M_{1},M_{2},\varphi)$ is -hard. ∎

See 1

###### Proof.

We prove both directions. The hardness case follows from Theorem 3. Indeed,
$\operatorname{PEqn}(G_{1},G_{2},\varphi)$ is a template of promise equations
over monoids (where the monoids just happen to be groups). Suppose that there
is no Abelian group homomorphism $\psi:G_{1}\rightarrow G_{2}$ that extends
$\varphi$. Observe that a monoid homomorphism between two groups must also be
a group homomorphism, so there is no Abelian monoid homomorphism
$\psi:G_{1}\rightarrow G_{2}$ that extends $\varphi$. Thus, by Theorem 3,
$\operatorname{PEqn}(G_{1},G_{2},\varphi)$ is NP-hard.

In the other direction, suppose that such a $\psi$ exists. We show that
$\operatorname{PEqn}(G_{1},G_{2},\varphi)$ is solved by AIP using Theorem 1.
Let $n$ be any odd arity and let $p:G_{1}^{n}\rightarrow G_{2}$ be the map
given by $p(g_{1},\dots,g_{n})\mapsto\prod_{i\in[n]}t_{i}$, where
$t_{i}=\psi(g_{i})$ for every odd $i$, and $t_{i}=\psi(g_{i})^{-1}$ for every
even $i$. Then $p$ is an alternating polymorphism of
$\operatorname{PEqn}(G_{1},G_{2},\varphi)$. ∎

##  6 Equations over Semigroups: Proof of Theorem 4

A _digraph_ ${\bm{D}}$ is a relational structure whose signature consists of a
single binary relation $E^{\bm{D}}$.

We follow closely the ideas from [33, Theorem 7]. That result states that
every CSP is polynomial-time equivalent to a problem of the form
$\operatorname{Eqn}(S,S)$ for some semigroup $S$. Their proof uses the fact
that every CSP is polynomial-time equivalent to another CSP whose template is
a digraph ${\bm{D}}$ with all singleton unary relations [25]. The fact that
they consider these unary relations on ${\bm{D}}$ yields equations in
$\operatorname{Eqn}(S,S)$ where all constants are allowed. For PCSPs, however,
this is our starting point.

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

For every template $({\bm{A}}_{1},{\bm{A}}_{2})$ there is a template
$({\bm{D}}_{1},{\bm{D}}_{2})$ of digraphs such that
$\operatorname{PCSP}({\bm{A}}_{1},{\bm{A}}_{2})$ is polynomial-time equivalent
to $\operatorname{PCSP}({\bm{D}}_{1},{\bm{D}}_{2})$.

The fact that we lack singleton unary relations in the templates
$({\bm{D}}_{1},{\bm{D}}_{2})$ is the main obstacle for applying the techniques
from [33]. We overcome this by extending our digraphs with an additional edge
joining two fresh distinguished vertices. The relational signature
$\sigma^{+}$ contains one binary relation symbol $E$, and two unary relation
symbols $P,Q$. Given a digraph ${\bm{D}}$, we write ${\bm{D}}^{+}$ for the
$\sigma^{+}$ structure defined by $D^{+}=D\cup\\{p,q\\}$, where $p$ and $q$
are fresh vertices, $E^{{\bm{D}}^{+}}=E^{{\bm{D}}}\cup\\{(p,q)\\}$,
$P^{{\bm{D}}^{+}}=\\{p\\}$, and $Q^{{\bm{D}}^{+}}=\\{q\\}$.

######  Lemma 3.

Let $({\bm{D}}_{1},{\bm{D}}_{2})$ be a template of digraphs. Then
$\operatorname{PCSP}({\bm{D}}_{1},{\bm{D}}_{2})$ is polynomial-time equivalent
to $\operatorname{PCSP}({\bm{D}}_{1}^{+},{\bm{D}}_{2}^{+})$.

###### Proof.

We give polynomial-time reductions in both directions. First, we reduce from
$\operatorname{PCSP}({\bm{D}}_{1},{\bm{D}}_{2})$ to
$\operatorname{PCSP}({\bm{D}}_{1}^{+},{\bm{D}}_{2}^{+})$. We consider two
cases. Suppose that $E^{{\bm{D}}_{2}}$ is empty. Then
$\operatorname{PCSP}({\bm{D}}_{1},{\bm{D}}_{2})$ amounts to deciding whether a
given instance ${\bm{I}}$ has an edge or not, which takes polynomial time.
Otherwise, assume that $E^{{\bm{D}}_{2}}$ is non-empty. Then our reduction
takes any instance ${\bm{I}}$ of
$\operatorname{PCSP}({\bm{D}}_{1},{\bm{D}}_{2})$ and considers it as an
instance of $\operatorname{PCSP}({\bm{D}}_{1}^{+},{\bm{D}}^{+}_{2})$. Clearly,
if ${\bm{I}}$ maps homomorphically to ${\bm{D}}_{1}$ then it also maps
homomorphically to ${\bm{D}}_{1}^{+}$ using the same homomorphism. Otherwise,
if ${\bm{I}}$ does not map homomorphically to ${\bm{D}}_{2}$ then it cannot
map homomorphically to ${\bm{D}}_{2}^{+}$. Indeed, to see this observe that
the digraph resulting from of ${\bm{D}}_{2}^{+}$ (by forgetting about the
$P,Q$ relations) maps homomorphically to ${\bm{D}}_{2}$: it suffices to send
the edge $(p,q)$ to an arbitrary edge in $E^{{\bm{D}}_{2}}$, which is non-
empty by assumption.

Now we describe a polynomial-time reduction from
$\operatorname{PCSP}({\bm{D}}_{1}^{+},{\bm{D}}_{2}^{+})$ to
$\operatorname{PCSP}({\bm{D}}_{1},{\bm{D}}_{2})$. The reduction considers an
instance ${\bm{I}}$ of
$\operatorname{PCSP}({\bm{D}}_{1}^{+},{\bm{D}}_{2}^{+})$ and checks in
polynomial time whether every connected component of ${\bm{I}}$ that
intersects $P^{\bm{I}}$ or $Q^{\bm{I}}$ maps homomorphically to the edge
structure $\bm{W}$ with $W=\\{p,q\\}$, $E^{\bm{W}}=\\{(p,q)\\}$,
$P^{\bm{W}}=\\{p\\}$, and $Q^{\bm{W}}=\\{q\\}$. If this is not the case,
${\bm{I}}$ is rejected. Otherwise, we remove from ${\bm{I}}$ the components
that intersect $P^{\bm{I}}$ or $Q^{\bm{I}}$. Next, we check in polynomial time
whether each remaining component of ${\bm{I}}$ can be mapped homomorphically
to $\bm{W}$, and removes the ones that do. If the resulting structure
${\bm{I}}^{\prime}$ is empty, then our reduction accepts ${\bm{I}}$.
Otherwise, observe that the resulting instance ${\bm{I}}^{\prime}$ is
equivalent to the original ${\bm{I}}$, in the sense that ${\bm{I}}$ maps to
${\bm{D}}_{i}^{+}$ if and only if ${\bm{I}}^{\prime}$ does so as well.
Furthermore, observe that a homomorphism from ${\bm{I}}^{\prime}$ to
${\bm{D}}_{i}^{+}$ cannot include $p$ and $q$ in its image, as there are no
components in ${\bm{I}}^{\prime}$ that map homomorphically to $\bm{W}$. This
means that ${\bm{I}}^{\prime}$ maps to ${\bm{D}}_{i}^{+}$ if and only if it
maps to ${\bm{D}}_{i}$. Hence, as the last step in our reduction we simply use
${\bm{I}}^{\prime}$ as an instance of
$\operatorname{PCSP}({\bm{D}}_{1},{\bm{D}}_{2})$. ∎

A semigroup $S$ is a _right-normal band_ if $ss=s$ for all $s\in S$ and
$rst=srt$ for all $r,s,t\in S$. Recall that we write $s\sim r$ if
$s\sqsubseteq r$ and $r\sqsubseteq s$ hold. It is easy to see that the
quotient $\widehat{S}=S/\sim$ inherits the semigroup structure from $S$.
Moreover, $\widehat{S}$ is a _semilattice_ , meaning that it is an Abelian
semigroup where every element is idempotent. Given an instance ${\bm{I}}$ of
$\operatorname{Eqn}(S,S)$ we denote by $\widehat{{\bm{I}}}$ the corresponding
instance over $\widehat{S}$, where every constant $s$ is substituted by its
$\sim$ class $\hat{s}$.

We need two lemmas from [33] and a simple observation.

######  Lemma 4 ([33]).

Let $S$ be a semilattice. Then $\operatorname{Eqn}(S,S)$ can be solved in
polynomial time. Moreover, if an instance ${\bm{I}}$ has a solution, it also
has a unique minimal one (with respect to the $\sqsubseteq$ preorder) that can
be obtained in polynomial time.

######  Lemma 5 ([33]).

Let $S$ be a right-normal band. Then an instance ${\bm{I}}$ of
$\operatorname{Eqn}(S,S)$ is solvable if it has a solution satisfying
$f(x)\in\hat{s}_{x}$, for all $x\in I$, where the map $x\mapsto\hat{s}_{x}$ is
the minimal solution of $\widehat{{\bm{I}}}$ in
$\operatorname{Eqn}(\widehat{S},\widehat{S})$.

######  Observation 2.

Let $S$ be a right-normal band, and let $s,s^{\prime},t\in S$ be three
arbitrary elements with $s\sim s^{\prime}$. Then $st=s^{\prime}t$.

###### Proof.

As $s\sim s^{\prime}$ and $S$ is right-normal, it must hold that
$s=s^{\prime}r^{\prime}$ and $s^{\prime}=sr$ for some $r,r^{\prime}\in S$.
Thus, $st=s^{\prime}r^{\prime}t=srr^{\prime}t$, and
$s^{\prime}t=srt=s^{\prime}r^{\prime}rt=srr^{\prime}rt=srr^{\prime}t$, where
the last equality holds since $S$ is a right-normal band. ∎

Let ${\bm{D}}$ be a digraph. We define a semigroup $S_{D}$ related to
${\bm{D}}$ in a similar fashion as [33]. The main difference is that we need
to “plant” a special subsemigroup $S_{W}$ inside $S_{D}$ that is used later as
the set of constants in our promise equations. The semigroup $S=S_{D}$ is a
right-normal band. It has the following $\sim$-classes:
$V^{\operatorname{L}},V^{\operatorname{R}},V^{\operatorname{LC}},V^{\operatorname{LR}},V^{\operatorname{CR}},E^{\operatorname{C}},0$,
described as follows. Given
$\square\in\\{\operatorname{L},\operatorname{R},\operatorname{LC},\operatorname{LR},\operatorname{CR}\\}$
the class $V^{\square}$ is a copy of $D\cup\\{p,q\\}$. That is,
$V^{\square}=\\{v^{\square}\mid v\in D\\}\cup\\{p^{\square},q^{\square}\\}$.
The class $E^{\operatorname{C}}$ is a copy of $E^{D}\cup\\{(p,q)\\}$, meaning
that $E^{\operatorname{C}}=\\{(u,v)^{\operatorname{C}}\mid(u,v)\in
E^{D}\\}\cup\\{(p,q)^{\operatorname{C}}\\}$. Finally, the class $0$ contains a
single element $0$. Observe that in a right-normal band $T$ it must hold that
$st=s^{\prime}t$ for all $s,s^{\prime},t\in T$ with $s\sim s^{\prime}$. Hence,
given a $\sim$-class $C\subseteq T$ and an element $t$ we abuse the notation
and write $Ct$ to denote the product of an arbitrary element from $C$ with
$t$. The product operation in $S$ is given by the following rules:

$\displaystyle
V^{\operatorname{R}}v^{\operatorname{L}}=V^{\operatorname{L}}v^{\operatorname{R}}=$
$\displaystyle
V^{\operatorname{LR}}v^{\operatorname{R}}=V^{\operatorname{LR}}v^{\operatorname{L}}=V^{\operatorname{L}}v^{\operatorname{LR}}=V^{\operatorname{R}}v^{\operatorname{LR}}=v^{\operatorname{LR}}$
$\displaystyle
V^{\operatorname{L}}v^{\operatorname{LC}}=V^{\operatorname{LC}}v^{\operatorname{L}}=E^{\operatorname{C}}v^{\operatorname{L}}=E^{\operatorname{C}}v^{\operatorname{LC}}=v^{\operatorname{LC}}$
$\displaystyle
V^{\operatorname{R}}v^{\operatorname{CR}}=V^{\operatorname{CR}}v^{\operatorname{R}}=E^{\operatorname{C}}v^{\operatorname{R}}=E^{\operatorname{C}}v^{\operatorname{CR}}=v^{\operatorname{CR}},$

where $v$ is an arbitrary element in $D\cup\\{p,q\\}$. Additionally,

$V^{\operatorname{L}}(u,v)^{\operatorname{C}}=V^{\operatorname{LC}}(u,v)^{\operatorname{C}}=u^{\operatorname{LC}},\quad\text{and}\quad
V^{\operatorname{R}}(u,v)^{\operatorname{C}}=V^{\operatorname{CR}}(u,v)^{\operatorname{C}}=v^{\operatorname{CR}},$

where $(u,v)$ belongs to $E^{D}\cup\\{(p,q)\\}$. Finally, all other products
not described above have $0$ as their result.

We define the subsemigroup $S_{W}\preceq S_{D}$ as the one containing the
elements $0,(p,q)^{\operatorname{C}},p^{\square},q^{\square}$ for
$\square\in\\{\operatorname{L},\operatorname{R},\operatorname{LC},\operatorname{LR},\operatorname{CR}\\}$.
Observe that for any digraph $D$, the quotient $\widehat{S_{D}}=S_{D}/\sim$ is
isomorphic to $\widehat{S_{W}}=S_{W}/\sim$.

######  Lemma 6.

There is a polynomial-time algorithm $\Phi$ that takes as an input a
$\sigma^{+}$-structure ${\bm{I}}$ and outputs a system of equations
$\Phi({\bm{I}})$ with constants in $S_{W}$ satisfying that for any digraph
${\bm{D}}$, ${\bm{I}}$ maps into ${\bm{D}}^{+}$ if and only if
$\Phi({\bm{I}})$ has a solution over $S_{D}$.

###### Proof.

This follows the first reduction in [33, Theorem 7] while making sure that all
constants remain in $S_{W}$. We construct the system $\Phi({\bm{I}})$. For
every vertex $v\in I$ we include variables
$v^{\operatorname{L}},v^{\operatorname{R}},v^{\operatorname{LR}}$. For each
$\square\in\\{\operatorname{L},\operatorname{R},\operatorname{LR}\\}$ we
include the constraint $v^{\square}\in V^{\square}$, which is a shorthand for
the equations $p^{\square}v^{\square}=v^{\square}$ and
$v^{\square}p^{\square}=p^{\square}$. We also include the equations
$p^{\operatorname{LR}}v^{\operatorname{L}}=v^{\operatorname{LR}}$ and
$p^{\operatorname{LR}}v^{\operatorname{R}}=v^{\operatorname{LR}}$. If $v\in
P^{\bm{I}}$ we include all constraints $v^{\square}=p^{\square}$ for
$\square\in\\{\operatorname{L},\operatorname{R},\operatorname{LR}\\}$.
Similarly, if $v\in Q^{\bm{I}}$, then we include the constraints of the form
$v^{\square}=q^{\square}$. For each edge $(u,v)\in E^{\bm{I}}$ we include a
variable $(u,v)^{\operatorname{C}}$ in $\Phi({\bm{I}})$, together with the
constraint $(u,v)^{\operatorname{C}}\in E^{\operatorname{C}}$, which is a
shorthand for the equations
$(u,v)^{\operatorname{C}}(p,q)^{\operatorname{C}}=(p,q)^{\operatorname{C}}$
and
$(p,q)^{\operatorname{C}}(u,v)^{\operatorname{C}}=(u,v)^{\operatorname{C}}$.
Finally, we also add the equations
$p^{\operatorname{LC}}(u,v)^{\operatorname{C}}=p^{\operatorname{LC}}u^{\operatorname{L}}$
and
$p^{\operatorname{CR}}(u,v)^{\operatorname{C}}=p^{\operatorname{CR}}v^{\operatorname{R}}$.
The resulting system $\Phi({\bm{I}})$ satisfies the statement of the theorem.
∎

######  Lemma 7.

There is a polynomial-time algorithm $\Psi$ that takes as an input a system of
equations $\bm{X}$ with constants in $S_{W}$ and produces one of the following
outcomes:

  1. (I)

It outputs a $\sigma^{+}$-structure $\Psi(\bm{X})$ that maps into
${\bm{D}}^{+}$ for any digraph ${\bm{D}}$ if and only if $\bm{X}$ has a
solution over $S_{D}$, or

  2. (II)

it rejects $\bm{X}$ and $\bm{X}$ has no solution over $S_{D}$ for any digraph
${\bm{D}}$.

###### Proof.

We describe the algorithm $\Psi$. This algorithm is meant to transform the
system $\bm{X}$ into a system of the form $\Phi({\bm{I}})$, for the algorithm
$\Phi$ given in Lemma 6 and some $\sigma^{+}$-structure ${\bm{I}}$. This time
we follow the second reduction in [33, Theorem 7] while making sure that all
constants in $\bm{X}$ remain in $S_{W}$ throughout all the transformations.

Without loss of generality, we may assume that every equation in $\bm{X}$ is
initially of the form $x_{1}x_{2}=x_{3}$, for some variables
$x_{1},x_{2},x_{3}$, or of the form $x=s$, for some variable $x$ and some
element $s\in S_{W}$. Consider the system $\widehat{\bm{X}}$ with constants in
$\widehat{S_{W}}=S_{W}/\sim$. By Lemma 4 we can find a minimal solution of
$\widehat{\bm{X}}$ in polynomial time. If such a solution does not exist, then
the system $\bm{X}$ is not satisfiable over $S_{D}$ for any digraph
${\bm{D}}$, and the algorithm $\Psi$ just rejects it. Otherwise, suppose that
the system $\widehat{\bm{X}}$ has some minimal solution. This solution maps
each variable $x\in X$ to a $\sim$-class $C_{x}$ of $S_{W}$. Consider an
arbitrary digraph ${\bm{D}}$. Using the observation that
$\widehat{S_{W}}\simeq\widehat{S_{D}}$ and Lemma 5, we deduce that $\bm{X}$
has a solution over $S_{D}$ if and only if it has a solution where the value
of each variable $x\in X$ belongs to the class $C_{x}$. Given a class $C_{x}$,
we define the constant $c_{x}\in S_{W}$ as

  * •

$p^{\square}$ if $C_{x}$ is the class $V^{\square}$ for
$\square\in\\{\operatorname{L},\operatorname{R},\operatorname{LC},\operatorname{LR},\operatorname{CR}\\}$,

  * •

$(p,q)^{\operatorname{C}}$ if $C_{x}=E^{\operatorname{C}}$, or

  * •

$0$ if $C_{x}=0$.

For each variable $x\in X$ we add the equations $c_{x}x=x$ and $xc_{x}=c_{x}$.
These equations are equivalent to the constraint that $x\in C_{x}$ (and we use
$x\in C_{x}$ as a shorthand for those equations), so the resulting system is
satisfiable over a semigroup $S_{D}$ if and only if the original one was.
Additionally, once every variable $x$ is constrained to take values inside
$C_{x}$, we can replace every equation of the form $x_{1}x_{2}=x_{3}$ in
$\bm{X}$ with the equation $c_{x_{3}}x_{2}=c_{x_{3}}x_{3}$ to yield an
equivalent system. Indeed, it must hold that $c_{x_{i}}x_{i}=x_{i}$, so the
equation $x_{1}x_{2}=x_{3}$ is equivalent to
$c_{x_{1}}x_{1}c_{x_{2}}x_{2}=c_{x_{3}}x_{3}$. Not only that, but $S_{D}$ is a
normal band and $x_{1}c_{x_{1}}=c_{x_{1}}$, so last equation is equivalent to
$c_{x_{1}}c_{x_{2}}x_{2}=c_{x_{3}}x_{3}$. Finally, the classes
$C_{x_{1}},C_{x_{2}},C_{x_{3}}$ were part of a solution to $\widehat{\bm{X}}$,
so it must be that $c_{x_{1}}c_{x_{2}}\sim c_{x_{3}}$, and by 2 it holds that
$c_{x_{1}}c_{x_{2}}x_{1}=c_{x_{3}}x_{1}$.

Every resulting equation of the form $0x_{1}=0x_{2}$ is trivially satisfied
and can be discarded. Consider a variable $x\in X$ whose corresponding class
$C_{x}$ is $0$. As we have removed every equation of the form $0x_{1}=0x_{2}$,
$x$ can only appear in constraints of the form $x\in 0$, and $x=0$. These are
trivially satisfiable by any assignment that maps $x$ to $0$, so we can remove
the variable $x$ and all equations containing it.

We are left with a system $\bm{X}$ where each variable is bound to a class
$V^{\square}$ for
$\square\in\\{\operatorname{L},\operatorname{R},\operatorname{LC},\operatorname{LR},\operatorname{CR}\\}$
or $E^{\operatorname{C}}$. Consider a variable $x\in X$ bound to the class
$V^{\operatorname{LC}}$. Suppose this variable appears in some equation of the
form $c_{1}x=c_{1}y$, and consider the class $C$ of $c_{1}$. By construction,
it must be that $C\sqsupseteq V^{\operatorname{LC}}$ in $\widehat{S_{W}}$.
However, we have removed all equations containing $0$, so the only possibility
left is that $C=V^{\operatorname{LC}}$. Suppose that we replace the
requirement $x\in V^{\operatorname{LC}}$ with $x\in V^{\operatorname{L}}$ and
every equation of the form $x=v^{\operatorname{LC}}$, where
$v^{\operatorname{LC}}\in S_{W}$ is a constant, with $x=v^{\operatorname{L}}$.
We claim the system $\bm{X}$ remains equivalent after these changes. Indeed,
this results from the observation that
$V^{\operatorname{LC}}v^{\operatorname{L}}=V^{\operatorname{LC}}v^{\operatorname{LC}}$
in any semigroup $S_{D}$ for any vertex $v\in D^{+}$. By the same logic we can
also replace any requirement of the kind $x\in V^{\operatorname{LR}}$ or $x\in
V^{\operatorname{CR}}$ with $x\in V^{\operatorname{CR}}$.

Consider any equation of the form $x=(u,v)^{\operatorname{C}}$ for a constant
$(u,v)^{\operatorname{C}}$. This equation is equivalent to the constraints
$p^{\operatorname{LC}}x=p^{\operatorname{LC}}y$,
$p^{\operatorname{CR}}x=p^{\operatorname{CR}}z$, $y=u^{\operatorname{L}}$ and
$z=v^{\operatorname{R}}$, where $y$ and $z$ are fresh variables.

Consider an equation of the form $cx=cy$, where both $x,y$ are constrained to
be in $c$’s $\sim$-class.
$(p,q)^{\operatorname{C}}x=(p,q)^{\operatorname{C}}y$, both This equation
holds if and only if $x=y$. Hence, we may remove this equation and identify
both variables $x,y$ together.

This far we have obtained a system $\bm{X}$ where each variable is bound to
either $V^{\operatorname{L}},V^{\operatorname{R}}$ or $E^{\operatorname{C}}$,
and the only constants are among
$p^{\operatorname{L}},p^{\operatorname{R}},q^{\operatorname{L}}$,
$q^{\operatorname{R}}$. Identifying variables and adding dummy variables if
necessary we can assume the following hold:

  * •

For each variable $x\in X$ constrained by $x\in E^{\operatorname{C}}$ there is
exactly one variable $x_{\operatorname{L}}$ constrained by
$x_{\operatorname{L}}\in V^{\operatorname{L}}$ in an equation of the form
$p^{\operatorname{LC}}x=p^{\operatorname{LC}}x_{\operatorname{L}}$, and
exactly one variable $x_{\operatorname{R}}$ constrained by
$x_{\operatorname{R}}\in V^{\operatorname{R}}$ that appears in an equation of
the form $p^{\operatorname{CR}}x=p^{\operatorname{CR}}x_{\operatorname{R}}$.

  * •

There are no two variables $x,y\in X$ constrained by $x,y\in
E^{\operatorname{C}}$ with $x_{\operatorname{L}}=y_{\operatorname{L}}$ and
$x_{\operatorname{R}}=y_{\operatorname{L}}$.

  * •

Not considering equations that are part of the constraints $x\in C$ for some
$\sim$-class $C$, each equation is of the form (i)
$p^{\operatorname{LR}}x=p^{\operatorname{LR}}y$ with $x\in
V^{\operatorname{L}}$ and $y\in V^{\operatorname{R}}$, (ii)
$p^{\operatorname{LC}}x=p^{\operatorname{LC}}x_{\operatorname{L}}$ or
$p^{\operatorname{CR}}x=p^{\operatorname{CR}}x_{\operatorname{R}}$ for some
$x\in E^{\operatorname{C}}$, or (iii) $x=p^{\square}$ or $x=q^{\square}$ for
$\square\in\\{\operatorname{L},\operatorname{R}\\}$.

One can see that such a system corresponds to $\Phi({\bm{I}})$ for some
$\sigma^{+}$-structure ${\bm{I}}$ that can be built in polynomial time. Then
$\Psi$ returns ${\bm{I}}$, which satisfies our requirements by Lemma 6. ∎

######  Corollary 4.

Let $({\bm{D}}_{1},{\bm{D}}_{2})$ be a template of digraphs. Then
$\operatorname{PCSP}({\bm{D}}_{1},{\bm{D}}_{2})$ is polynomial-time equivalent
to $\operatorname{PEqn}(S_{D_{1}},S_{D_{2}},\varphi)$, where
$\varphi=\operatorname{id}_{S_{W}}$.

###### Proof.

We show that $\operatorname{PEqn}(S_{D_{1}},S_{D_{2}},\varphi)$ is polynomial-
time equivalent to $\operatorname{PCSP}({\bm{D}}_{1}^{+},{\bm{D}}_{2}^{+})$,
which suffices by Lemma 3. Observe that algorithm $\Phi$ given in Lemma 7 is a
polynomial-time reduction from
$\operatorname{PCSP}({\bm{D}}_{1}^{+},{\bm{D}}_{2}^{+})$ to
$\operatorname{PEqn}(S_{D_{1}},S_{D_{2}},\varphi)$, and algorithm $\Psi$,
given in Lemma 6 is a polynomial-time reduction in the other direction. ∎

Corollary 4 and Theorem 8 establish Theorem 4.

## References

  * [1] Kristina Asimi and Libor Barto.  Finitely tractable promise constraint satisfaction problems.  In Proc. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS’21), volume 202 of LIPIcs, pages 11:1–11:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.  arXiv:2010.04618, doi:10.4230/LIPIcs.MFCS.2021.11.
  * [2] Albert Atserias and Víctor Dalmau.  Promise constraint satisfaction and width.  In Proc. 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA’22), pages 1129–1153, 2022.  arXiv:2107.05886, doi:10.1137/1.9781611977073.48.
  * [3] Per Austrin, Venkatesan Guruswami, and Johan Håstad.  (2+$\epsilon$)-Sat is NP-hard.  SIAM J. Comput., 46(5):1554–1573, 2017.  doi:10.1137/15M1006507.
  * [4] Libor Barto, Diego Battistelli, and Kevin M. Berg.  Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case.  In Proc. 38th International Symposium on Theoretical Aspects of Computer Science (STACS’21), volume 187 of LIPIcs, pages 10:1–10:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.  arXiv:2010.04623, doi:10.4230/LIPIcs.STACS.2021.10.
  * [5] Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal.  Algebraic approach to promise constraint satisfaction.  J. ACM, 68(4):28:1–28:66, 2021.  arXiv:1811.00970, doi:10.1145/3457606.
  * [6] Libor Barto and Marcin Kozik.  Combinatorial Gap Theorem and Reductions between Promise CSPs.  In Proc. 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA’22), pages 1204–1220, 2022.  arXiv:2107.09423, doi:10.1137/1.9781611977073.50.
  * [7] Amey Bhangale and Subhash Khot.  Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups.  In Proc. 53rd Annual ACM Symposium on Theory of Computing (STOC’21), pages 1615–1628. ACM, 2021.  arXiv:2009.02815, doi:10.1145/3406325.3451003.
  * [8] Amey Bhangale, Subhash Khot, and Dor Minzer.  On Approximability of Satisfiable k-CSPs: II.  In Proc. 55th Annual ACM Symposium on Theory of Computing (STOC’23), pages 632–642. ACM, 2023.  doi:10.1145/3564246.3585120.
  * [9] Amey Bhangale, Subhash Khot, and Dor Minzer.  On Approximability of Satisfiable k-CSPs: III.  In Proc. 55th Annual ACM Symposium on Theory of Computing (STOC’23), pages 643–655. ACM, 2023.  doi:10.1145/3564246.3585121.
  * [10] Manuel Bodirsky.  Complexity of infinite-domain constraint satisfaction, volume 52.  Cambridge University Press, 2021.
  * [11] Manuel Bodirsky and Martin Grohe.  Non-dichotomies in Constraint Satisfaction Complexity.  In Proc. 35th International Colloquium on Automata, Languages and Programming (ICALP’08), volume 5126 of Lecture Notes in Computer Science, pages 184–196. Springer, 2008.  doi:10.1007/978-3-540-70583-3\\_16.
  * [12] Manuel Bodirsky and Thomas Quinn-Gregson.  Solving equation systems in $\omega$-categorical algebras.  J. Math. Log., 21(3), 2021.  doi:10.1142/S0219061321500203.
  * [13] Joshua Brakensiek and Venkatesan Guruswami.  Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.  SIAM J. Comput., 50(6):1663–1700, 2021.  arXiv:1704.01937, doi:10.1137/19M128212X.
  * [14] Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep.  Conditional Dichotomy of Boolean Ordered Promise CSPs.  TheoretiCS, 2, 2023.  arXiv:2102.11854, doi:10.46298/theoretics.23.2.
  * [15] Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep.  SDPs and robust satisfiability of promise CSP.  In Proc. 55th Annual ACM Symposium on Theory of Computing (STOC’23), pages 609–622. ACM, 2023.  arXiv:2211.08373, doi:10.1145/3564246.3585180.
  * [16] Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný.  The power of the combined basic LP and affine relaxation for promise CSPs.  SIAM J. Comput., 49:1232–1248, 2020.  arXiv:1907.04383, doi:10.1137/20M1312745.
  * [17] Alex Brandts and Stanislav Živný.  Beyond PCSP(1-in-3,NAE).  Information and Computation, 2022.  arXiv:2104.12800, doi:10.1016/j.ic.2022.104954.
  * [18] Andrei Bulatov, Peter Jeavons, and Andrei Krokhin.  Classifying the complexity of constraints using finite algebras.  SIAM J. Comput., 34(3):720–742, 2005.  doi:10.1137/S0097539700376676.
  * [19] Andrei A. Bulatov.  Complexity of conservative constraint satisfaction problems.  ACM Trans. Comput. Log., 12(4):24:1–24:66, 2011.  doi:10.1145/1970398.1970400.
  * [20] Andrei A. Bulatov.  A dichotomy theorem for nonuniform CSPs.  In Proc. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS’17), pages 319–330, 2017.  arXiv:1703.03021, doi:10.1109/FOCS.2017.37.
  * [21] Lorenzo Ciardo and Stanislav Živný.  Approximate graph colouring and the hollow shadow.  In Proc. 55th Annual ACM Symposium on Theory of Computing (STOC’23), pages 623–631. ACM, 2023.  arXiv:2211.03168, doi:10.1145/3564246.3585112.
  * [22] Lorenzo Ciardo and Stanislav Živný.  CLAP: A new algorithm for promise CSPs.  SIAM J. Comput., 52(1):1–37, 2023.  arXiv:2107.05018, doi:10.1137/22M1476435.
  * [23] Victor Dalmau and Jakub Opršal.  Local consistency as a reduction between constraint satisfaction problems.  2023\.  arXiv:2301.05084.
  * [24] Lars Engebretsen, Jonas Holmerin, and Alexander Russell.  Inapproximability results for equations over finite groups.  Theor. Comput. Sci., 312(1):17–45, 2004.  doi:10.1016/S0304-3975(03)00401-8.
  * [25] Tomás Feder and Moshe Y. Vardi.  The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory.  SIAM J. Comput., 28(1):57–104, 1998.  doi:10.1137/S0097539794266766.
  * [26] Miron Ficak, Marcin Kozik, Miroslav Olšák, and Szymon Stankiewicz.  Dichotomy for Symmetric Boolean PCSPs.  In Proc. 46th International Colloquium on Automata, Languages, and Programming (ICALP’19), volume 132, pages 57:1–57:12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019.  arXiv:1904.12424, doi:10.4230/LIPIcs.ICALP.2019.57.
  * [27] M. R. Garey and David S. Johnson.  The complexity of near-optimal graph coloring.  J. ACM, 23(1):43–49, 1976.  doi:10.1145/321921.321926.
  * [28] Mikael Goldmann and Alexander Russell.  The complexity of solving equations over finite groups.  Inf. Comput., 178(1):253–262, 2002.  doi:10.1006/INCO.2002.3173.
  * [29] Martin Grohe.  The complexity of homomorphism and constraint satisfaction problems seen from the other side.  J. ACM, 54(1):1–24, 2007.  doi:10.1145/1206035.1206036.
  * [30] Johan Håstad.  Some optimal inapproximability results.  J. ACM, 48(4):798–859, 2001.  doi:10.1145/502090.502098.
  * [31] Pavol Hell and Jaroslav Nešetřil.  On the complexity of H-coloring.  J. Comb. Theory, Ser. B, 48(1):92–110, 1990.  doi:10.1016/0095-8956(90)90132-J.
  * [32] Peter G. Jeavons, David A. Cohen, and Marc Gyssens.  Closure properties of constraints.  J. ACM, 44(4):527–548, 1997.  doi:10.1145/263867.263489.
  * [33] Ondřej Klíma, Pascal Tesson, and Denis Thérien.  Dichotomies in the complexity of solving systems of equations over finite semigroups.  Theory Comput. Syst., 40(3):263–297, 2007.  doi:10.1007/S00224-005-1279-2.
  * [34] Phokion G. Kolaitis and Moshe Y. Vardi.  Conjunctive-query containment and constraint satisfaction.  J. Comput. Syst. Sci., 61(2):302–332, 2000.  doi:10.1006/jcss.2000.1713.
  * [35] Michael Kompatscher.  The equation solvability problem over supernilpotent algebras with Mal’cev term.  International Journal of Algebra and Computation, 28(06):1005–1015, 2018.  doi:10.1142/S0218196718500443.
  * [36] Andrei Krokhin, Jakub Opršal, Marcin Wrochna, and Stanislav Živný.  Topology and adjunction in promise constraint satisfaction.  SIAM J. Comput., 52(1):37–79, 2023.  arXiv:2003.11351, doi:10.1137/20M1378223.
  * [37] Benoît Larose and László Zádori.  Taylor terms, constraint satisfaction and the complexity of polynomial equations over finite algebras.  Int. J. Algebra Comput., 16(3):563–582, 2006.  doi:10.1142/S0218196706003116.
  * [38] Dániel Marx.  Tractable hypergraph properties for constraint satisfaction and conjunctive queries.  J. ACM, 60(6), 2013.  Article No. 42.  arXiv:0911.0801, doi:10.1145/2535926.
  * [39] Peter Mayr.  On the complexity dichotomy for the satisfiability of systems of term equations over finite algebras.  In Proc. 48th International Symposium on Mathematical Foundations of Computer Science (MFCS’23), volume 272 of LIPIcs, pages 66:1–66:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.  doi:10.4230/LIPICS.MFCS.2023.66.
  * [40] Tamio-Vesa Nakajima and Stanislav Živný.  Linearly ordered colourings of hypergraphs.  ACM Trans. Comput. Theory, 13(3–4), 2022.  arXiv:2204.05628, doi:10.1145/3570909.
  * [41] Tamio-Vesa Nakajima and Stanislav Zivný.  Boolean symmetric vs. functional PCSP dichotomy.  In Proc. 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’23), 2023.  doi:10.1109/LICS56636.2023.10175746.
  * [42] Thomas Schaefer.  The complexity of satisfiability problems.  In Proc. 10th Annual ACM Symposium on the Theory of Computing (STOC’78), pages 216–226, 1978.  doi:10.1145/800133.804350.
  * [43] Steve Seif and Csaba Szabó.  Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem.  J. Complex., 19(2):153–160, 2003.  doi:10.1016/S0885-064X(02)00027-4.
  * [44] Dmitriy Zhuk.  A proof of the CSP dichotomy conjecture.  J. ACM, 67(5):30:1–30:78, 2020.  arXiv:1704.01914, doi:10.1145/3402029.

##  Appendix A Reduction to Special Equations

By definition, instances of $\operatorname{Eqn}(S,T)$ can be seen as systems
of equations over $S$ where all constants belong to $T$. Any system of
equations can be transformed into an equivalent system by adding new variables
and breaking larger equations into smaller ones until every equation is of the
form $x_{1}x_{2}=x_{3}$, for three variables $x_{1},x_{2},x_{3}$, or of the
form $x=t$ for a variable $x$ and some constant $t\in T$. For instance, the
equation

$x_{1}c_{1}x_{2}c_{2}\dots x_{k}c_{k}=c_{k+1},$

where all $c_{1},\dots,c_{k+1}\in T$ can be transformed into the system

$\displaystyle x_{1}y=x,\quad\quad y=c_{1},$ $\displaystyle xc_{2}\dots
x_{k}^{\epsilon_{k}}c_{k}=c_{k+1},$

where $x,y$ are fresh variables. Applying these steps in succession yields a
system where every equation is of the desired form.

When considering equations over groups the same idea works, but one needs to
take into account inverted variables $x^{-1}$. Given a system of equations
over a group $G$ with constants in a subgroup $H\preceq G$, we can substitute
any instance of the inverted variable $x^{-1}$ with instances of a fresh
variable $y$ after adding the equations $xy=z$, $z=e$ to the system, where $z$
is another fresh variable.

##  Appendix B Missing Proofs from Section 3

The next result establishes finite tractability of promise equations, as
advertised in Section 3.

######  Lemma 8.

Assume that $\operatorname{PEqn}(M_{1},M_{2},\varphi)$ is tractable. Then it
is finitely tractable.

###### Proof.

By Theorem 3 there must be some Abelian homomorphism $\psi:M_{1}\rightarrow
M_{2}$ extending $\varphi$ and $\operatorname{Im}(\psi)$ is a union of
subgroups. Let $M\preceq M_{2}$ be the submonoid $\operatorname{Im}(\psi)$. By
assumption $M$ is Abelian and a union of subgroups. Let $N\preceq M$ the
submonoid $\operatorname{Im}(\varphi)$. We claim that
$\operatorname{Eqn}(M,N)$ is solvable in polynomial time. Indeed, consider the
map $\operatorname{id}_{M}$. This map is an Abelian endomorphism of $M$, whose
image is a union of subgroups. Moreover, $\operatorname{id}_{M}$ extends
$\operatorname{id}_{N}$, so by Theorem 3 $\operatorname{Eqn}(M,N)$ is solvable
in polynomial time via $\textsc{BLP}+\textsc{AIP}$.

The idea now is that $\operatorname{Eqn}(M,N)$ can be “sandwiched” by the
template $({\bm{A}},{\bm{B}})$ (defined in Definition 2) of
$\operatorname{PEqn}(M_{1},M_{2},\varphi)$. To make this formal, we need to
produce a template ${\bm{C}}$ in the same signature as ${\bm{A}}$ and
${\bm{B}}$ such that $\operatorname{CSP}({\bm{C}})$ is
$\operatorname{Eqn}(M,N)$ up to relabeling some relations. The set $C$ equals
$M$. The relation $R_{\times}^{\bm{C}}$ consists of the triples
$(s_{1},s_{2},s_{3})\in M^{3}$ such that $s_{1}s_{2}=s_{3}$. Finally, for each
$s\in\mathrm{dom}(\varphi)$ we define $R_{s}^{\bm{C}}=\\{\varphi(s)\\}$.
Clearly, it holds that ${\bm{A}}\mapsto{\bm{C}}\mapsto{\bm{B}}$: the map
$\psi$ is a homomorphism from ${\bm{A}}$ to ${\bm{C}}$, and the inclusion map
is a homomorphism from ${\bm{C}}$ to ${\bm{B}}$. On the other hand,
$\operatorname{CSP}({\bm{C}})$ is easily seen to be equivalent to
$\operatorname{Eqn}({\bm{C}})$. Indeed, we can obtain
$\operatorname{Eqn}({\bm{C}})$ from ${\bm{C}}$ by relabeling each relation
$R_{s}$ to $R_{\varphi(s)}$ and removing duplicate relations, which clearly
does not change the complexity of the related CSP. ∎

The next lemma show that $\textsc{BLP}+\textsc{AIP}$ is necessary in Theorem
3.

######  Lemma 9.

Let $G$ be an arbitrary Abelian group. Let $M$ be the monoid resulting from
adding to $G$ a fresh element $e$ that serves as the monoid identity. Then
$\operatorname{Eqn}(M,M)$ is solvable by $\textsc{BLP}+\textsc{AIP}$ but not
by AIP.

###### Proof.

The fact that $\textsc{BLP}+\textsc{AIP}$ solves the $\operatorname{Eqn}(M,M)$
follows by Theorem 3 from the fact that $M$ is Abelian and a union of
subgroup. To rule out AIP, we show that $\operatorname{Eqn}(M,M)$ has no
alternating polymorphisms; this suffices by Theorem 1. We begin with the
following observation. Let $p:M^{n}\rightarrow M$ be a polymorphism where the
$i$-th coordinate is inessential. Consider the homomorphism $\tau_{p,i}$ that
sends each element $s\in M$ to $p(e,\dots,s,\dots,e)$, where all arguments are
equal to $e$ except for the $i$-th one, which is equal to $s$. Then it must be
that $\tau_{p,i}$ is constant and equal to $e$. Now suppose that $p$ is a
$(2n+1)$-ary alternating polymorphism. Then define
$q(x_{1},\dots,x_{2n})=p(x_{1},x_{1},x_{2},x_{3},\dots,x_{2n-1})$. As $p$ is
alternating, the first coordinate is inessential in $q$. By our previous
observation, this means that $\tau_{p,1}(s)\tau_{p,2}(s)=e$ for all $s\in M$.
Observe that the only way that the product of two elements equals $e$ in $M$
is that both elements are equal to $e$. This means that both $\tau_{p,1}$ and
$\tau_{p,2}$ are constant and equal to $e$. However, as $p$ is alternating,
this also means that $p$ itself must be constant and equal to $e$. This
contradicts the fact that $p$ must be idempotent, so such alternating
polymorphism cannot exist to begin with. ∎

##  Appendix C Missing Proofs from Section 5

First we prove a characterisation of polymorphisms for monoids.

See 1

###### Proof.

We show the statement for the semigroup, monoid and the group case. The
semigroup case is straightforward: $p$ is a polymorphism if and only if it
preserves $R_{\times}$ and $R_{s}$ for all $s\in\mathrm{dom}(\varphi)$.
Preserving $R_{\times}$ is equivalent to preserving the product operation from
$Z_{1}^{n}$ to $Z_{2}$, and preserving $R_{s}$ means that
$p(s,\dots,s)=\varphi(s)$.

The monoid case follows in the same way, noting that multiplicative identities
must be preserved because $\mathrm{dom}(\varphi)$ is a submonoid of $Z_{1}$,
so $e_{Z_{1}}\in\mathrm{dom}(\varphi)$ and
$p(e_{Z_{1}},\dots,e_{Z_{1}})=\varphi(e_{Z_{1}})=e_{Z_{2}}$, where the last
identity uses the fact that $\varphi$ is a monoid homomorphism, so it
preserves multiplicative identities.

Finally, the group case is shown as the monoid case by noting that preserving
inverse elements is just a consequence of preserving the product operation and
multiplicative identities. ∎

Next we prove various characterisations of regularity.

See 2

###### Proof.

(3) $\implies$ (2):

For any finite group $G$ there exists number $k>1$ such that $g^{k}=g$ for all
$g\in G$.

(2) $\implies$ (3):

Consider the set $G=\\{s^{\ell}\mid 1\leq\ell<k\\}$. We claim that $G$ is a
group whose identity is $s^{k-1}$. (2), $s^{k-1}$ acts as a multiplicative
identity in $G$. Moreover, given any $1\leq\ell<k-1$, the inverse of
$s^{\ell}$ in $G$ is simply $s^{k-1-\ell}$.

(2) $\implies$ (1):

Let $t=s^{k-2}$, where $s^{0}$ is just $e$. Then we have $sst=sts=e$.

(1) $\implies$ (4):

By the definition of regularity, there is some element $t$ such that
$s^{2}t=s$, meaning that $s\sqsubseteq s^{2}$.

(4) $\implies$ (2):

By assumption, $s^{2}t=s$ for some $t\in M$. Note that this implies that
$s^{k+1}t^{k}=s$ for all $k\geq 1$. Let $k>1$ be the smallest number such that
$s^{k}=s^{\ell}$ for some $\ell<k$, and let $\ell$ be the smallest number
witnessing $s^{k}=s^{\ell}$. Then, the following chain of identities holds

$s=s^{k}t^{k-1}=s^{\ell}t^{k-1}=s^{\ell}t^{\ell-1}t^{k-\ell}=st^{k-\ell}.$

In particular, this means that $s^{k^{\prime}}=s^{k^{\prime}}t^{k-\ell}$ for
any $k^{\prime}\geq 1$. Finally, it also holds that
$s=s^{k-\ell+1}t^{k-\ell}$, which together with the last equality yields that
$s=s^{k-\ell+1}$. Since $\ell<k$, we have $k-\ell+1>1$, thus establishing (4).

∎

##  Appendix D Explicit Templates: Proof of Theorem 6

We describe a bijective minion homomorphism
$\xi:\operatorname{Pol}({\bm{A}},{\bm{B}})\rightarrow\mathscr{M}_{M,a}$. Let
us introduce some notation before the start. We identify the powerset
$2^{[n]}$ with the set of tuples $\\{0,1\\}^{n}$ by associating each set
$S\subseteq[n]$ to the $n$-tuple whose $i$-th entry is one if and only if
$i\in S$ (i.e., the characteristic vector of $S$). Thus, we see a $n$-ary
polymorphism $p\in\operatorname{Pol}({\bm{A}},{\bm{B}})$ as a map from
$2^{[n]}$ to $\mathscr{M}_{M,a}(2)$. Following this convention, three sets
$X_{1},X_{2},X_{3}\subseteq[n]$ belong to the relation $R^{{\bm{A}}^{n}}$ if
and only if they are a partition of $[n]$. Similarly, the unary relation
$C_{0}^{{\bm{A}}^{n}}$ contains only the empty set, and $C_{1}^{{\bm{A}}^{n}}$
contains only the total set $[n]$.

Let us carry on with the description of $\xi$. Given a $n$-ary polymorphism
$p\in\operatorname{Pol}({\bm{A}},{\bm{B}})$, $\xi$ maps it to the tuple
$\bm{b_{p}}=(b_{p,1},\dots,b_{p,n})\in\mathscr{M}_{M,a}$ defined as follows.
For each $i\in[n]$, let $(c_{i,1},c_{i,2})=p(\\{i\\})$. Then we set
$b_{p,i}=c_{i,1}$. In order to prove that $\xi$ is a bijective minion
homomorphism we need to show that (I) $\bm{b_{p}}$ is an element of
$\mathscr{M}_{M,a}$ for all polymorphisms $p$, (II) that $\xi$ preserves minor
operations, and (III) that $\xi$ is a bijection.

Before moving on with the rest of the proof, we recall the definition of
$R^{\bm{B}}$:

$\displaystyle((r_{1},s_{1}),(r_{2},s_{2}),(r_{3},s_{3}))\in R^{\bm{B}}\text{
if and only if }$ $\displaystyle r_{1},r_{2},r_{3}\text{ commute pairwise, and
}s_{1}=r_{2}r_{3},\quad s_{2}=r_{3}r_{1},\quad s_{3}=r_{1}r_{2}.$ (1)

Below we prove some claims about the map $\xi$ and polymorphisms of
$({\bm{A}},{\bm{B}})$ that are used to show (I), (II), and (III). Fix some
$n$-ary polymorphism $p$.

Claim 1: $b_{p,i}$ and $b_{p,j}$ commute in $M$ for any $1\leq i<j\leq n$.

Fix different indices $i,j\in[n]$. Clearly, the sets
$\\{i\\},\\{j\\},[n]\setminus\\{i,j\\}$ form a partition of $[n]$, so
$(p(\\{i\\}),p(\\{j\\}),p([n]\setminus\\{i,j\\})$ must belong to $R^{\bm{B}}$.
Thus, there are elements $r_{1},r_{2},r_{3}\in M$ witnessing Equation 1. In
particular, $b_{p,i}=r_{1}$ and $b_{p,j}=r_{2}$, so $b_{p,i}$ and $b_{p,j}$
commute, establishing the claim.

Claim 2: Let $(c_{1},c_{2})=p(X)$ for some $X\subseteq{[n]}$. Then
$p({[n]}\setminus X)=(c_{2},c_{1})$ .

Observe that $(X,[n]\setminus X,\emptyset)\in R^{{\bm{A}}^{n}}$ so the image
of this triple through $p$ belongs to $R^{\bm{B}}$. Hence, there are elements
$r_{1},r_{2},r_{3}\in M$ witnessing Equation 1. It also holds that
$p(\emptyset)=(e,a)$, so $r_{3}=e$, and $p(X)=(r_{1},r_{2})$, $p([n]\setminus
X)=(r_{2},r_{1})$, as desired.

Claim 3: Let $(b_{1},b_{2})=p(X)$ $(c_{1},c_{2})=p(Y)$ $(d_{1},d_{2})=p(X\cup
Y)$ for two disjoint sets $X,Y\subseteq{[n]}$. Then $d_{1}=b_{1}c_{1}$.

Indeed, consider the set $Z=[n]\setminus(X\cup Y)$. By our previous claim it
holds that $p(Z)=(d_{2},d_{1})$. Moreover, it holds that $(X,Y,Z)\in
R^{{\bm{A}}^{n}}$, so using the characterisation given in Equation 1 we obtain
that $d_{1}=b_{1}c_{1}$, as desired.

Claim 4: $\prod_{i=1^{n}}b_{p,i}=a$

Observe that $[n]$ is the disjoint union of the singleton sets $\\{i\\}$ for
each $i\in[n]$. Using Claim 3 iteratively, we obtain that
$\prod_{i=1^{n}}b_{p,i}$ equals the first element of the pair $p([n])=(a,e)$,
proving the claim.

Now we move on to proving (I), (II), and (III). Claims 1 and 4 show that for
any $n$-ary polymorphism $p\in\operatorname{Pol}({\bm{A}},{\bm{B}})$, the
tuple $(b_{p,i})_{i=0}^{n}$ is an element of $\mathscr{M}_{M,a}$, as stated in
(I). As for fact (II), consider some $n$-ary polymorphism
$p\in\operatorname{Pol}({\bm{A}},{\bm{B}})$, some map $\pi:[n]\rightarrow[m]$,
and the minor $q=p^{(\pi)}$. The fact that $\xi$ preserves minors is
equivalent to $b_{q,i}=\prod_{j\in\pi^{-1}(i)}b_{p,j}$ for all $i\in[m]$. We
show now that this is the case. By definition, $b_{q,i}$ is the first element
of the pair $q(\\{i\\})=p(\pi^{-1}(i))$. However, expressing $\pi^{-1}(i)$ as
a disjoint union of singletons and using Claim 3 we obtain that the first
element of $p(\pi^{-1}(i))$ is the product of the first elements of the pairs
$p(\\{j\\})$ for each $j\in\pi^{-1}$, as we wanted to show.

So far we have established that $\xi$ is indeed a minion homomorphism,
following (I) and (II). Lastly, we prove that $\xi$ is a bijection, as stated
in (III). To see that $\xi$ is surjective, consider a tuple
$(b_{1},\dots,b_{n})\in\mathscr{M}_{M,a}(n)$. Then the map
$p:2^{n}\mapsto\mathscr{M}_{M,a}(n)$ given by

$X\mapsto(\prod_{i\in X}b_{i},\prod_{i\in[n]\setminus X}b_{i})$

is a polymorphism of $({\bm{A}},{\bm{B}})$. Not only that but
$\xi(p)=(b_{1},\dots,b_{n})$. In the other direction, to prove that $\xi$ is
injective, we show that an $n$-ary polymorphism
$p\in\operatorname{Pol}({\bm{A}},{\bm{B}})$ is completely determined by
$(b_{p,1},\dots,b_{p,n})$. Consider an arbitrary set $X\subseteq[n]$, and let
$p(X)=(c,d)$. Expressing $X$ as a disjoint union of singletons and using Claim
3 we obtain that $c=\prod_{i\in X}b_{p,i}$. Additionally, by Claim 2 we know
that $p([n]\setminus X)=(d,c)$ and using the same argument as before we obtain
that $d=\prod_{i\in[n]\setminus X}b_{p,i}$. Thus, $p(X)$ is completely given
by the tuple $(b_{p,1},\dots,b_{p,n})$, showing that $\xi$ is injective.