IsRepresentable}}({\mathcal{K}})$ and $\operatorname{\text{\sc
NeedMoreForkWitnesses}}({\mathcal{K}})$ ensure that whenever (27) holds at the
start of an iteration of the for loop, $R$ together with
$b\in\\{a_{1},\dots,a_{k}\\}$ is a correct input for $\operatorname{\text{\sc
IsRepresentable}}({\mathcal{K}})$, and the new version of $R$ produced also
satisfies (27); similarly, whenever (27) holds at the start of an iteration of
the while loop, $R$ is a correct input for $\operatorname{\text{\sc
NeedMoreForkWitnesses}}({\mathcal{K}})$, and the new version of $R$ produced
also satisfies (27).

For (3), notice that the for loop is repeated exactly $k$ times, and the while
loop is iterated as long as new designated pairs of fork witnesses can be
added to $R$ by such an iteration. By statement (1) above, all these pairs of
fork witnesses are witnessing forks in $\mathbf{B}$ in coordinates
$\mathsf{d},\dots,n$, therefore their number is at most
$\mathsf{a}_{\mathcal{K}}^{2}(n-\mathsf{d})$, where
$\mathsf{a}_{\mathcal{K}}:=\max\\{|\mathbf{A}|:\mathbf{A}\in{\mathcal{K}}\\}$.
Hence, after at most $\mathsf{a}_{\mathcal{K}}^{2}(n-\mathsf{d})$ iterations
of the while loop in Steps 6–8, we have to get a NO answer, and exit the loop.

Let $R_{1}$ denote the version of $R$ after Step 8, and let $R_{2}$ denote the
$R$ returned at the end of Algorithm 4 in Step 16. We will prove that $R_{2}$
is a standardized representation for $\mathbf{B}$ by showing that $R_{1}$ and
$R_{2}$ satisfy conditions (1)–(3) of Lemma 18. Clearly, in Steps 9–15 of
Algorithm 4 exactly those new fork witnesses are added to $R_{1}$ which yield
$R_{2}$ so that condition (3) of Lemma 18 is satisfied. Since (27) holds for
$R=R_{1}$, and every element $R_{2}\setminus R_{1}$ is obtained from elements
of $R_{1}$ by applying the term $p$, we have that $R_{0}\subseteq
R_{1}\subseteq R_{2}\subseteq\mathbf{B}$. This proves condition (1) of Lemma
18. It remains to prove condition (2).

Let $\overline{R}_{1}$ denote the set of all elements of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ that are completely
representable by $R_{1}$. By Corollary 13, $R_{1}\subseteq\mathbf{B}$ implies
that $\overline{R}_{1}\subseteq\mathbf{B}$. Next we want to prove that
$\overline{R}_{1}$ is in fact a subalgebra of $\mathbf{B}$. Let $f\in F$ be an
operation symbol, say $f$ is $\ell$-ary, let
$b_{1},\dots,b_{\ell}\in\overline{R}_{1}$, and let
$b:=f(b_{1},\dots,b_{\ell})$. We need to show that $b\in\overline{R}_{1}$.
Since $b_{1},\dots,b_{\ell}\in\overline{R}_{1}$, i.e., $b_{1},\dots,b_{\ell}$
are completely representable by $R_{1}$, there exist
$(u_{j}^{(\mathsf{d})},\widehat{u}_{j}^{(\mathsf{d})},\dots,u_{j}^{(n)},\widehat{u}_{j}^{(n)},\overline{w_{j}^{I}})$
for $j\in[\ell]$ such that conditions (2)–(4) in the description of
$\operatorname{\text{\sc NeedMoreForkWitnesses}}({\mathcal{K}})$ hold for
$R=R_{1}$. By the choice of $f$ and definition of $b$ above, we have that
actually, all conditions (1)–(5) in the description of
$\operatorname{\text{\sc NeedMoreForkWitnesses}}({\mathcal{K}})$ hold for
$R=R_{1}$. Since $R_{1}$ is the version of $R$ in Step 8 of Algorithm 4, the
last iteration of the while loop ran with $R=R_{1}$ and produced the answer
NO. Thus, $b$ must be completely representable by $R_{1}$, which proves that
$b\in\overline{R}_{1}$. Finally, notice that the for loop in Steps 2–5 of
Algorithm 4 ensure that the generators $a_{1},\dots,a_{k}$ of $\mathbf{B}$
belong to $\overline{R}_{1}$. Thus, $\overline{R}_{1}=\mathbf{B}$, so
condition (2) of Lemma 18 also holds. This completes the proof of the
correctness of Algorithm 4.

To estimate the running time of Algorithm 4, recall that Algorithm 2 runs in
$O(n^{\mathsf{d}})$ time, so this is the running time of Step 1. In Steps 2–5,
Algorithm 1 is called $k$ times, and each iteration runs in
$O(n^{\mathsf{d}+2})$ time, therefore the completion of Steps 2–5 requires
$O(kn^{\mathsf{d}+2})$ time. As we saw earlier in this proof, in Steps 6–8 the
oracle $\operatorname{\text{\sc NeedMoreForkWitnesses}}({\mathcal{K}})$ is
called $O(n)$ times, therefore the running time of these steps is $O(n)$.
Finally, in Steps 9–15, the double for loop is iterated $O(n)$ times, and each
iteration requires $O(n)$ time. Therefore, Steps 9–15 require $O(n^{2})$ time.
Hence, the overall running time of Algorithm 4 is $O(kn^{\mathsf{d}+2})$.

###  4.4. $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ is in $\mathsf{NP}$.

The main result of this subsection is the following theorem.

######  Theorem 20.

Let $a_{1},\dots,a_{k},b\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
$(\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}})$ be an input for
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$. If $b$ is in the subalgebra of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by
$\\{a_{1},\dots,a_{k}\\}$, then there exists a term $t$ in the language $F$ of
${\mathcal{K}}$ such that

  * •

$t(a_{1},\dots,a_{k})=b$ and

  * •

$\mathsf{Circ}_{F}(t)$ has size $O(kn^{\mathsf{d}+2})$.

Consequently, $\operatorname{\text{\sc SMP}}({\mathcal{K}})\in\mathsf{NP}$.

The proof relies on Lemma 21 below, which shows that by recording the
computations Algorithm 4 performs on a given input $a_{1},\dots,a_{k}$, we can
build a polynomial size circuit that produces a standardized representation
for the algebra with generators $a_{1},\dots,a_{k}$. The precise statement is
as follows.

######  Lemma 21.

Let $a_{1},\dots,a_{k}\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ with
$\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}$ $(n\geq\mathsf{d})$, and
let $\mathbf{B}$ be the subalgebra of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by
$\\{a_{1},\dots,a_{k}\\}$. There exists an $F$-circuit $C$ with the following
properties:

  1. (1)

$C$ has $k$ input nodes and $O(n^{\mathsf{d}-1})$ labeled output nodes such
that for the input $a_{1},\dots,a_{k}$, the collection of outputs of $C$ —
together with the labeling of the outputs — is a standardized representation
$R$ for $\mathbf{B}$ computed by Algorithm 4.

  2. (2)

The size of $C$ is $O(kn^{\mathsf{d}+2})$.

######  Proof 4.6.

$C$ will be constructed in five phases, the first four of which produce
$F\cup\\{P\\}$-circuits, which correspond to Step 1, Steps 2–5, Steps 6–8 and
Steps 9–15 of Algorithm 4.

In Step 1, i.e., during the execution of Algorithm 2 on the input
$a_{1},\dots,a_{k}$, for every choice of $I\in\binom{[n]}{\mathsf{d}-1}$ and
$\overline{b}\in\mathbf{B}|_{I}$, the designated local witness
$r_{I,\overline{b}}\in R$ is obtained as
$r_{I,\overline{b}}:=t_{I,\overline{b}}(a_{1},\dots,a_{k})$ for a term
$t_{I,\overline{b}}$ (in the language $F$) such that
$\overline{b}=t_{I,\overline{b}}(a_{1}|_{I},\dots,a_{k}|_{I})$. Since
$\bigl{|}\mathbf{B}|_{I}\bigr{|}\leq\mathsf{a}_{{\mathcal{K}}}^{\mathsf{d}-1}$
for every such $I$, where
$\mathsf{a}_{{\mathcal{K}}}:=\max\\{|\mathbf{A}|:\mathbf{A}\in{\mathcal{K}}\\}$
is a constant independent of $a_{1},\dots,a_{k}$, the terms
$t_{I,\overline{b}}$ can be chosen to be of constant size
($\leq\mathsf{a}_{{\mathcal{K}}}^{\mathsf{d}-1}$). Therefore, an $F$-circuit
$C_{1}$ which, for the input $a_{1},\dots,a_{k}$, computes the partial
standardized representation obtained in Step 1 of Algorithm 4 (i.e., a full
set of designated local witnesses for $\mathbf{B}$) can be constructed as
follows: $C_{1}$ is the disjoint union of the $F$-circuits
$\mathsf{Circ}(t_{I,\overline{b}})$, except that they all have the same input
nodes for $a_{1},\dots,a_{k}$. The output $r_{I,\overline{b}}$ of each
$\mathsf{Circ}(t_{I,\overline{b}})$ is an output of $C_{1}$ as well, with the
appropriate label recording its designation. Clearly, $C_{1}$ has size
$O(n^{\mathsf{d}-1})$.

In Steps 2–5, Algorithm 1 is run on each input tuple
$b\in\\{a_{1},\dots,a_{k}\\}$ together with the partial standardized
representation $R$ constructed by that point in the algorithm (which contains
a full set of designated local witnesses for $\mathbf{B}$ by Step 1). By
Remark 15, each of these $k$ applications of Algorithm 1 is a computation that
can be performed by the $P$-circuit $\mathsf{Circ}^{+}(T_{n})$ on designated
local witnesses in $R$ and on appropriately chosen designated fork witnesses,
some of which are added to $R$ during the computation. Therefore, an
$F\cup\\{P\\}$-circuit $C_{2}$ which, for the inputs $a_{1},\dots,a_{k}$,
computes the partial standardized representation for $\mathbf{B}$ obtained in
Step 5 of Algorithm 4 can be constructed as follows: add to $C_{1}$ $k$
disjoint copies of the $P$-circuit $\mathsf{Circ}^{+}(T_{n})$ described in
Remark 15, one for each choice of $b\in\\{a_{1},\dots,a_{k}\\}$, so that their
input nodes are the appropriate designated local witnesses and fork witnesses
computed earlier or during the evaluation of $T_{n}$ as described in Remark
15, and they have appropriately labeled output nodes for every pair of
designated fork witnesses added to $R$. It follows from Remark 15 that $C_{2}$
has size $O(n^{\mathsf{d}-1})+k\cdot
O(n^{\mathsf{d}+1})=O(kn^{\mathsf{d}+1})$.

Similarly, in Steps 6–8, in every iteration of the while loop where the output
of $\operatorname{\text{\sc NeedMoreForkWitnesses}}({\mathcal{K}})$ has the
form

$X=\bigl{(}\textrm{YES},f,\bigl{(}(u_{j}^{(\mathsf{d})},\widehat{u}_{j}^{(\mathsf{d})},\dots,u_{j}^{(n)},\widehat{u}_{j}^{(n)},\overline{w_{j}^{I}})\bigr{)}_{j=1}^{\ell},b_{1},\dots,b_{\ell},b,\widetilde{R}\bigr{)}$

such that conditions (1)–(7) in the description of $\operatorname{\text{\sc
NeedMoreForkWitnesses}}({\mathcal{K}})$ are satisfied, the fork witnesses
$u_{j}^{(m)},\widehat{u}_{j}^{(m)}$ and local witnesses $w_{j}^{I}$ had
already been included in the current version of $R$, $b_{1},\dots,b_{\ell}$
and $b$ can be computed as stated in conditions (4)–(5), and Algorithm 1 can
be run on $b$ (and the current version of $R$) to find the fork witnesses that
have to be added to $R$ to get $\widetilde{R}$ (the new $R$). We saw in the
proof of Theorem 19 that the while loop is iterated at most $O(n)$ times.
Therefore, an $F\cup\\{P\\}$-circuit $C_{3}$ which, for the input
$a_{1},\dots,a_{k}$, computes the partial standardized representation for
$\mathbf{B}$ obtained in Step 8 of Algorithm 4 can be constructed as follows:
add to $C_{2}$, one after the other, as many as necessary (at most $O(n)$)
circuits of the following form:

  * $\circ$

$\ell$ disjoint copies of the $P$-circuit $\mathsf{Circ}(T_{n})$ whose inputs
are (already computed) fork and local witnesses
$u_{j}^{(\mathsf{d})},\widehat{u}_{j}^{(\mathsf{d})},\dots,u_{j}^{(n)},\widehat{u}_{j}^{(n)},\overline{w_{j}^{I}}$
($j\in[\ell]$), and

  * $\circ$

whose outputs $b_{1},\dots,b_{\ell}$ are the inputs for an $f$-gate, which
produces $b$,

  * $\circ$

followed by a copy of the $P$-circuit $\mathsf{Circ}^{+}(T_{n})$ from Remark
15 with appropriately labeled output nodes for every pair of designated fork
witnesses added to $R$, as described in Remark 15.

Since the $P$-circuits $\mathsf{Circ}(T_{n})$ and $\mathsf{Circ}^{+}(T_{n})$
have size $O(n^{\mathsf{d}+1})$ by (14) and Remark 15, and the arities $\ell$
of the operation symbols $f$ are bounded by a constant independent of the
input, we get that the size of $C_{3}$ is

$O(kn^{\mathsf{d}+1})+O(n)\cdot\bigl{(}\ell\cdot
O(n^{\mathsf{d}+1})+1+O(n^{\mathsf{d}+1})\bigr{)}=O(kn^{\mathsf{d}+2}).$

Finally, to compute the additional fork witnesses included in $R$ in Steps
9–15 of Algorithm 4, we have to add at most $O(n)$ many $P$-circuits to
$C_{3}$, each one of size $1$ or $3$ (see the definition of $p$ in (4)).

The resulting $F\cup\\{P\\}$-circuit, $C_{4}$, is therefore of size
$O(kn^{\mathsf{d}+2})$. Finally, since $P$ is a term in $F$, gates of type $P$
can be easily eliminated from $C_{4}$ by replacing each of them with the
corresponding $F$-circuit (of constant size). Thus we obtain an $F$-circuit
$C$ from $C_{4}$ which satisfies conditions (1)–(2) of the lemma.

######  Proof 4.7 (Proof of Theorem 20).

To prove the first statement of the theorem, consider an input
$a_{1},\dots,a_{k},b\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
$(\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}})$ for
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$, let $\mathbf{B}$ denote the
subalgebra of $\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by
$\\{a_{1},\dots,a_{k}\\}$, and assume that $b\in\mathbf{B}$. For
$n<\mathsf{d}$ the assertion of the theorem is trivial — by the same argument
that we used in the second paragraph of the proof of Lemma 21 — since
$|\mathbf{B}|\leq\mathsf{a}_{{\mathcal{K}}}^{\mathsf{d}-1}$ for a constant
$\mathsf{a}_{{\mathcal{K}}}$ that depends only on ${\mathcal{K}}$. Therefore,
we will assume from now on that $n\geq\mathsf{d}$.

Let $C$ be a circuit satisfying properties (1)–(2) of Lemma 21, and let $R$
denote the standardized representation for $\mathbf{B}$ that is computed by
$C$ from $a_{1},\dots,a_{k}$. As we noted in Remark 12, Lemma 10 shows that if
$b\in\mathbf{B}$, then the equality (17),

$b=T_{n}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(n)},\widehat{u}^{(n)},\overline{b^{I})},$

holds with all arguments of $T_{n}$ members of $R$; namely, each pair
$u^{(m)},\widehat{u}^{(m)}$ ($m=\mathsf{d},\dots,n$) is designated to witness
a derived fork in the $m$-th coordinate, and the tuple $\overline{b^{I}}$
($I\in\binom{[n]}{\mathsf{d}-1}$) consists of some designated local witnesses
for $\mathbf{B}$. Hence, $C$ has a subcircuit $U$ which outputs exactly the
arguments of $T_{n}$ in the above expression for $b$. Since $C$ is an
$F$-circuit of size $O(kn^{d+2})$, so is $U$. Identifying the outputs of $U$
with the inputs of an $F$-circuit for $T_{n}$, which is obtained from its
$P$-circuit by replacing each $P$-gate by the corresponding $F$-circuit, we
get an $F$-circuit for a term $t$ such that $t(a_{1},\dots,a_{k})=b$. The size
of $\mathsf{Circ}_{F}(T_{n})$ is constant times the size of
$\mathsf{Circ}_{P}(T_{n})$, which is $O(n^{d+1})$ by (14) (for $e=1$).
Therefore the size of $\mathsf{Circ}_{F}(t)$ is
$O(kn^{\mathsf{d}+2})+O(n^{\mathsf{d}+1})=O(kn^{\mathsf{d}+2})$. This proves
the first statement of Theorem 20.

By this statement, we have a polynomial size certificate for “$b$ is in the
subalgebra generated by $\\{a_{1},\dots,a_{k}\\}$” for every input
$a_{1},\dots,a_{k},b$ for $\operatorname{\text{\sc SMP}}({\mathcal{K}})$. This
proves that $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ lies in
$\mathsf{NP}$.

######  Remark 22.

In Theorem 20, the term $t$ witnessing that $b$ belongs to the subalgebra
generated by $a_{1},\dots,a_{k}$ clearly has depth polynomial in $n$. In the
case that the $\mathsf{d}$-cube term is a Mal’tsev term, this was already
observed in [22, Theorem 2.2]. If the $\mathsf{d}$-cube term is a near-
unanimity term, then the fact that $b$ belongs to the subalgebra generated by
$a_{1},\dots,a_{k}$ can be witnessed by polynomially many terms of constant
length by the Baker–Pixley Theorem [1]. It is however open in the general
case, whether a polynomial bound can be imposed on the length of a
representation of $t$ by a term rather than by a circuit, as in Theorem 20.

###  4.5. Finding compact representations: The relationship between
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$ and $\operatorname{\text{\sc
CompactRep}}({\mathcal{K}})$

The main result of this section is the following theorem.

Algorithm 5 Reduction of $\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$
to $\operatorname{\text{\sc SMP}}({\mathcal{K}})$

0: $a_{1},\dots,a_{k}\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ with
$\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}$, $n\geq\mathsf{d}$

0: Standardized representation $R$ for the subalgebra $\mathbf{B}$ of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by
$a_{1},\dots,a_{k}$

1: Run Algorithm 2 for $\operatorname{\text{\sc LocalRep}}({\mathcal{K}})$
with input $a_{1},\dots,a_{k}\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
and $\theta_{i}=0$ ($i\in[n]$) to get output $R_{0}$

2: $R:=R_{0}$

3: for $i=\mathsf{d},\dots,n$ and $\gamma\in\mathbf{B}|_{i}$ do

4: find $b\in R_{0}$ with $b|_{i}=\gamma$

5: for $\beta\in\mathbf{B}|_{i}$ do

6: let $c\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{i}$ be such that
$c|_{[i-1]}=b|_{[i-1]}$ and $c|_{i}=\beta^{\gamma}$

7: run $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ with input
$a_{1}|_{[i]},\dots,a_{k}|_{[i]},c\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{i}$

8: if answer is YES then

9: for $j=i+1,\dots,n$ do

10: find $c_{j}\in A_{j}$ such that $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$ with input
$a_{1}|_{[j]},\dots,a_{k}|_{[j]},(c,c_{j})\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{j}$
answers YES

11: $c:=(c,c_{j})$

12: end for

13: add $b,c$ to $R$, and designate them to witness the fork
$(\gamma,\beta^{\gamma})\in\operatorname{\text{\sc fork}}_{i}(R)$.

14: end if

15: end for

16: end for

17: return $R$

Algorithm 6 Reduction of $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ to
$\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$

0: $a_{1},\dots,a_{k},b\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ with
$\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}$, $n\geq\mathsf{d}$

0: Is $b$ in the subalgebra $\mathbf{B}$ of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by
$a_{1},\dots,a_{k}$?

1: Run $\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$ with input
$a_{1},\dots,a_{k}$, and let $R$ be its output (a standardized representation
for $\mathbf{B}$)

2: for $I\in\binom{[n]}{\mathsf{d}-1}$ do

3: if $R$ contains no designated witness for $b|_{I}$ then

4: return NO

5: end if

6: end for

7: Run Algorithm 1 for $\operatorname{\text{\sc
IsRepresentable}}({\mathcal{K}})$ with input $b,R$, to get output
$(\textsf{A},S^{\prime},S)$ with $\textsf{A}=\textrm{YES}$ or
$\textsf{A}=\textrm{NO}$

8: return A

######  Theorem 23.

The problems $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ and
$\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$ are polynomial time
reducible to one another. In more detail, Algorithm 5 solves
$\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$ in polynomial time by
repeated calls of $\operatorname{\text{\sc SMP}}({\mathcal{K}})$, and
Algorithm 6 solves $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ (for inputs
satisfying $n\geq\mathsf{d}$) in polynomial time by a single call of
$\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$.

######  Proof 4.8.

As we mentioned earlier, $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ for
inputs $a_{1},\dots,a_{k},b$ that are $n$-tuples with $n<\mathsf{d}$ can be
solved in constant time, since the algebra $\mathbf{B}$ generated by
$a_{1},\dots,a_{k}$ has size bounded by a constant that depends only on
${\mathcal{K}}$. Therefore it will not restrict generality to assume
$n\geq\mathsf{d}$ for the inputs of $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$ in Algorithm 6, and the first statement of Theorem 23
will follow from the second statement on Algorithms 5 and 6.

First we will discuss Algorithm 5. To prove its correctness, note that Step 1
produces a partial standardized representation $R_{0}$ for $\mathbf{B}$, which
is a full set of designated local witnesses for $\mathbf{B}$. Elements without
designations are not added to $R=R_{0}$ later on in Algorithm 5, therefore we
will be done if we show that Steps 3–16 add to $R$ a pair of designated
witnesses (from $\mathbf{B}$) for all derived forks of $\mathbf{B}$ in
coordinates $\geq\mathsf{d}$, and possibly for some non-derived forks as well,
but nothing else is added to $R$.

Lines 3–7 show that the loop in Steps 3–16 examines each pair
$(\gamma,\beta)\in\mathbf{B}|_{i}\times\mathbf{B}|_{i}$ for every
$i=\mathsf{d},\dots,n$, finds $b=(b_{1},\dots,b_{n})\in R_{0}\,(\subseteq
R\subseteq B)$ such that $b_{i}=\gamma$, and checks — using
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$ — whether or not the tuple
$c=(b_{1},\dots,b_{i-1},\beta^{\gamma})$ is in the subalgebra
$\mathbf{B}|_{[i]}$ generated by the elements
$a_{1}|_{[i]},\dots,a_{k}|_{[i]}$. If the answer is YES, then $B$ contains a
tuple of the form
$(c,c_{i+1},\dots,c_{n})=(b_{1},\dots,b_{i-1},\beta^{\gamma},c_{i+1},\dots,c_{n})$
for some $c_{j}\in A_{j}$ ($j=i+1,\dots,n$), which will be found, coordinate-
by-coordinate, by repeated applications of $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$ in Steps 9–12. It is clear that in this case $b,c$ are
in $\mathbf{B}$ and witness that $(\gamma,\beta^{\gamma})$ is a fork in $B$,
so these witnesses are correctly added to $R$ in Step 13. This is the only
step when $R$ changes, so this shows that the $R$ returned in Step 17 is a
partial standardized representation for $\mathbf{B}$.

It remains to show that $R$ contains designated witnesses for all derived
forks of $\mathbf{B}$ in coordinates $\geq\mathsf{d}$. Let $\mathsf{d}\leq
i\leq n$, and let $(\gamma,\beta^{\gamma})\in\operatorname{\text{\sc
fork}}_{i}^{\prime}(B)$ with $(\gamma,\beta)\in\operatorname{\text{\sc
fork}}_{i}(B)$. By statement (2) of Lemma 3, for every choice of
$b\in\mathbf{B}$ with $b|_{i}=\gamma$ there exists an element $\widehat{b}$
such that $b$ and $\widehat{b}$ are witnesses for the derived fork
$(\gamma,\beta^{\gamma})\in\operatorname{\text{\sc fork}}_{i}^{\prime}(B)$,
that is, such that $\widehat{b}|_{[i-1]}=b|_{[i-1]}$ and
$\widehat{b}|_{i}=\beta^{\gamma}$. Hence, for the $b$ and for the $i$-tuple
$c=\widehat{b}|_{[i]}$ found in Steps 4 and 6 of Algorithm 5,
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$ in Step 7 has to give the
answer YES, and the $n$-tuple $c$ produced in Steps 8–12 and added to $R$ in
Step 13, along with $b$, to witness
$(\gamma,\beta^{\gamma})\in\operatorname{\text{\sc fork}}_{i}^{\prime}(R)$ is
such a $\widehat{b}$. This finishes the proof of the correctness of Algorithm
5.

In Step 1, Algorithm 2 runs in $O(n^{\mathsf{d}})$ time. Steps 3–16 require
running $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ $O(n^{2})$ times on
inputs not larger than the input for Algorithm 5, and adding one pair of
witnesses to $R$ no more than $O(n)$ times. This show that Algorithm 5 reduces
$\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$ to
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$ in $O(n^{\mathsf{d}})$ time.

Now we turn to Algorithm 6. The algorithm starts with a call to
$\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$ to compute a
standardized representation $R$ for the algebra $\mathbf{B}$ generated by the
input tuples $a_{1},\dots,a_{k}$. A necessary condition for the input tuple
$b$ to be in $\mathbf{B}$ is that $b|_{I}\in\mathbf{B}|_{I}$ for all
$I\in\binom{[n]}{\mathsf{d}-1}$. Since $R$ contains a full set of designated
local witnesses for $\mathbf{B}$, $b$ will satisfy this necessary condition if
and only if $R$ contains designated local witnesses for all projections
$b|_{I}$ $\bigl{(}I\in\binom{[n]}{\mathsf{d}-1}\bigr{)}$ of $b$. This is being
checked in Steps 2–6 of Algorithm 6; if the condition fails for some
$I\in\binom{[n]}{\mathsf{d}-1}$, the algorithm returns the correct answer NO,
meaning, $b\notin\mathbf{B}$.

If the algorithm passes Steps 2–6 without returning NO, then $b,R$ is a
correct input for $\operatorname{\text{\sc IsRepresentable}}({\mathcal{K}})$,
which checks in Step 7 whether $b$ is representable by $R$. Since every tuple
representable by $R$ must be in $\mathbf{B}$, and conversely, by Remark 12,
every element of $\mathbf{B}$ is representable by $R$, we get that the YES/NO
answer provided by $\operatorname{\text{\sc IsRepresentable}}({\mathcal{K}})$
is the correct answer to $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ for
the given input. This shows the correctness of Algorithm 6.

Steps 2–6 of Algorithm 6 run in $O(n^{\mathsf{d}-1})$ time, while
$\operatorname{\text{\sc IsRepresentable}}({\mathcal{K}})$ in Step 7 requires
$O(n^{\mathsf{d}+2})$ time. Thus, Algorithm 6 reduces $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$ to $\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$
in $O(n^{\mathsf{d}+2})$ time.

##  5\. Structure Theory and the Subpower Membership Problem

Our global assumption for this section is the following:

${\mathcal{V}}$ is a variety with a $\mathsf{d}$-cube term, or equivalently,
with a $(1,\mathsf{d}-1)$-parallelogram term ($\mathsf{d}>1$).

As in Section 3, we do not assume that the algebras we are considering are
finite, or have a finite language, so the results in this section hold for
arbitrary algebras.

One of the main results of [16] is a structure theorem for the critical
subalgebras of finite powers of algebras with a cube (or parallelogram) term.
In this section we adapt this structure theorem to find a new representation
(different from compact representations) for subalgebras of products of
algebras in a variety ${\mathcal{V}}$ with a cube term. In the next section,
this representation will be used to prove the main result of the paper.

To restate the results from [16] that we need here, we introduce some
terminology and notation. Let $\mathbf{R}$ be a subalgebra of a product
$\mathbf{A}^{(1)}\times\dots\times\mathbf{A}^{(n)}$ of some algebras
$\mathbf{A}^{(1)},\dots,\mathbf{A}^{(n)}\in{\mathcal{V}}$. Let
$\mathbf{A}_{i}:=\mathbf{R}|_{i}$ for each $i\in[n]$, and let
$\mathbf{C}:=\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$. So, $\mathbf{R}$
is a _subdirect subalgebra_ of $\mathbf{C}$.

We say that $\mathbf{R}$ is a _critical subalgebra_ of
$\mathbf{A}^{(1)}\times\dots\times\mathbf{A}^{(n)}$ if it has the following
two properties:

  * •

$\mathbf{R}$ is _completely $\cap$-irreducible_ in the lattice of subalgebras
of $\mathbf{A}^{(1)}\times\dots\times\mathbf{A}^{(n)}$, that is, whenever
$\mathbf{R}$ is an intersection of a family of subalgebras $\mathbf{S}_{j}$
($j\in J$) of $\mathbf{A}^{(1)}\times\dots\times\mathbf{A}^{(n)}$, we have
that $\mathbf{R}=\mathbf{S}_{j}$ for some $j\in J$; and

  * •

$\mathbf{R}$ is _directly indecomposable_ in the following sense: $[n]$ cannot
be partitioned into two nonempty sets $I$ and $J$ such that $\mathbf{R}$ and
$\mathbf{R}|_{I}\times\mathbf{R}|_{J}$ differ only by a permutation of
coordinates.

Note that if $\mathbf{R}$ is completely $\cap$-irreducible, it will not have a
direct decomposition $\mathbf{R}|_{I}\times\mathbf{R}|_{J}$ (up to a
permutation of coordinates) where $\mathbf{R}|_{I}$ and $\mathbf{R}|_{J}$ are
both proper subalgebras of the corresponding products $\prod_{i\in
I}\mathbf{A}^{(i)}$ and $\prod_{i\in J}\mathbf{A}^{(i)}$, respectively.
However, $\mathbf{R}$ may be completely $\cap$-irreducible and still directly
decomposable as $\mathbf{R}|_{I}\times\mathbf{R}|_{J}$ (up to a permutation of
coordinates) if, say, $\mathbf{R}|_{J}=\prod_{i\in J}\mathbf{A}^{(i)}$ and
$\mathbf{R}|_{I}$ is a completely $\cap$-irreducible subalgebra of
$\prod_{i\in I}\mathbf{A}^{(i)}$.

Now let us assume that $\mathbf{R}$ is a critical subalgebra of
$\mathbf{A}^{(1)}\times\dots\times\mathbf{A}^{(n)}$. Continuing with the
notation introduced in the second to last paragraph, let us choose and fix
$\delta_{i}\in\operatorname{Con}(\mathbf{A}_{i})$ ($i\in[n]$) such that
$\delta:=\delta_{1}\times\dots\times\delta_{n}$ is the largest product
congruence of $\mathbf{C}$ with the property that $\mathbf{R}$ is a
$\delta$-saturated subalgebra of $\mathbf{C}$. (Such a congruence exists,
because the join of product congruences of $\mathbf{C}$ is a product
congruence, and if $\mathbf{R}$ is saturated with respect to a family of
congruences of $\mathbf{C}$, then it is saturated with respect to their join.)
With this notation, let
$\overline{\mathbf{R}}:=\mathbf{R}/\delta_{\mathbf{R}}$, and let
$\overline{\mathbf{A}}_{i}:=\mathbf{A}_{i}/\delta_{i}$ $(i\in[n])$; we call
$\overline{\mathbf{R}}$ _the reduced representation of $\mathbf{R}$_.

Theorems 2.5 and 4.1 of [16] yield a structure theorem for the critical
subalgebras of finite powers $\mathbf{A}^{n}$ of an arbitrary algebra
$\mathbf{A}\in{\mathcal{V}}$. The relevant proofs in [16], namely the proofs
of Theorem 2.5 (and its preparatory Lemmas 2.1, 2.3, 2.4) and Theorem 3.6
(part (3), implication $\Rightarrow$), carry over without any essential
changes to the more general situation when instead of subalgebras of powers
$\mathbf{A}^{n}$ with $\mathbf{A}\in{\mathcal{V}}$ we consider subalgebras of
products $\mathbf{A}^{(1)}\times\dots\times\mathbf{A}^{(n)}$ with
$\mathbf{A}^{(1)},\dots,\mathbf{A}^{(n)}\in{\mathcal{V}}$. Thus, we get the
theorem below, where we state only those parts of the structure theorem that
we need later on, retaining the numbering from [16, Theorem 2.5]. The
superscript ♭ in (6)♭ indicates that instead of the original condition (6) we
state a weaker condition which is sufficient for our purposes.

######  Theorem 24 (Cf. [16]).

Let $\mathbf{A}^{(1)},\dots,\mathbf{A}^{(n)}\in{\mathcal{V}}$, and let
$\overline{\mathbf{R}}$ be the reduced representation of a critical subalgebra
$\mathbf{R}$ of $\mathbf{A}^{(1)}\times\dots\times\mathbf{A}^{(n)}$. If
$n\geq\mathsf{d}$, then the following hold.

  1. (1)

$\overline{\mathbf{R}}\leq\prod_{i=1}^{n}\overline{\mathbf{A}}_{i}$ is a
representation of $\overline{\mathbf{R}}$ as a subdirect product of
subdirectly irreducible algebras $\overline{\mathbf{A}}_{i}$.

  2. (6)♭

$\overline{\mathbf{A}}_{i}$ and $\overline{\mathbf{A}}_{j}$ are similar for
any $i,j\in[n]$ (see Section 2.3).

  3. (7)

If $n>2$, then each $\overline{\mathbf{A}}_{i}$ has abelian monolith $\mu_{i}$
$(i\in[n])$.

  4. (8)

For the centralizers $\rho_{\ell}:=(0:\mu_{\ell})$ of the monoliths
$\mu_{\ell}$ $(\ell\in[n])$, the image of the composite map

$\overline{\mathbf{R}}\stackrel{{\scriptstyle\operatorname{proj}_{ij}}}{{\rightarrow}}\overline{\mathbf{A}}_{i}\times\overline{\mathbf{A}}_{j}\twoheadrightarrow\overline{\mathbf{A}}_{i}/\rho_{i}\times\overline{\mathbf{A}}_{j}/\rho_{j}.$

is the graph of an isomorphism
$\overline{\mathbf{A}}_{i}/\rho_{i}\to\overline{\mathbf{A}}_{j}/\rho_{j}$ for
any distinct $i,j\in[n]$.

Note that the homomorphism in part (8) is the same as in [16, Theorem 2.5
(8)]; the slightly different description presented here will be more
convenient later on.

Now we are ready to discuss our representation theorem. Let
$\mathbf{B}_{1},\dots,\mathbf{B}_{n}$ be nontrivial algebras in
${\mathcal{V}}$, and let $\mathbf{B}$ be a subdirect subalgebra of
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$.

First, we replace each $\mathbf{B}_{j}$ ($j\in[n]$) by its image under the
embedding

$\mathbf{B}_{j}\hookrightarrow\prod_{\sigma\in\operatorname{Irr}(\mathbf{B}_{j})}\mathbf{B}_{j}/\sigma,\quad\qquad
x_{j}\mapsto(x_{j}/\sigma)_{\sigma\in\operatorname{Irr}(\mathbf{B}_{j})};$
(28)

thus, each $\mathbf{B}_{j}$ is replaced by a subdirect product of all of its
subdirectly irreducible quotients $\mathbf{B}_{j}/\sigma$. To set up a more
convenient notation, let

$W:=\\{(j,\sigma):j\in[n],\sigma\in\operatorname{Irr}(\mathbf{B}_{j})\\},$

and for each $j\in[n]$, let
$W_{j}:=\\{j\\}\times\operatorname{Irr}(\mathbf{B}_{j})$; thus,
$W=W_{1}\cup\dots\cup W_{n}$. Furthermore, for each $w=(j,\sigma)\in W$ let
$\widehat{\mathbf{B}}_{w}:=\mathbf{B}_{j}/\sigma$, and for every element
$x_{j}$ in $\mathbf{B}_{j}$ let $\widehat{x}_{w}:=x_{j}/\sigma$. Then the
product of the embeddings (28) for all $j\in[n]$ yields an embedding

$\widehat{\phantom{\mathbf{B}}}\colon\prod_{j\in[n]}\mathbf{B}_{j}\hookrightarrow\prod_{w\in
W}\widehat{\mathbf{B}}_{w},\qquad
x=(x_{j})_{j\in[n]}\mapsto\widehat{x}:=(\widehat{x}_{w})_{w\in W}.$

We will denote the image of $\mathbf{B}$ under this embedding
$\widehat{\phantom{n}}$ by $\widehat{\mathbf{B}}$. By construction,
$\widehat{\mathbf{B}}$ is a subdirect product of the subdirectly irreducible
algebras $\widehat{\mathbf{B}}_{w}$ ($w\in W$); in particular,
$\widehat{\mathbf{B}}_{w}=\widehat{\mathbf{B}}|_{w}$ for all $w\in W$. For
each $w\in W$ let $\mu_{w}$ denote the monolith of $\widehat{\mathbf{B}}_{w}$
and $\rho_{w}$ its centralizer $(0:\mu_{w})$.

Next we define a relation $\sim$ on $W$ as follows: we require $\sim$ to be
reflexive, and for distinct $v,w\in W$ we define $v\sim w$ to hold if and only
if

  * •

the subdirectly irreducible algebras $\widehat{\mathbf{B}}_{v}$ and
$\widehat{\mathbf{B}}_{w}$ are similar with abelian monoliths $\mu_{v}$ and
$\mu_{w}$, and

  * •

the image of $\widehat{\mathbf{B}}|_{vw}$ under the natural map
$\widehat{\mathbf{B}}_{v}\times\widehat{\mathbf{B}}_{w}\twoheadrightarrow(\widehat{\mathbf{B}}_{v}/\rho_{v})\times(\widehat{\mathbf{B}}_{w}/\rho_{w})$
is the graph of an isomorphism
$\widehat{\mathbf{B}}_{v}/\rho_{v}\to\widehat{\mathbf{B}}_{w}/\rho_{w}$.

It is easy to see that $\sim$ is an equivalence relation on $W$.

Our representation theorem describes the algebra $\mathbf{B}$ in terms of its
image $\widehat{\mathbf{B}}$, namely, it shows that $\widehat{\mathbf{B}}$ is
determined by its projections onto small sets of coordinates (i.e., small
subsets of $W$) and by its projections onto the blocks of $\sim$. A block of
$\sim$ may be large, but the image of $\widehat{\mathbf{B}}$ under a
projection onto a block of $\sim$ has a special structure.

######  Theorem 25.

Let ${\mathcal{V}}$ be a variety with a $\mathsf{d}$-cube term, let
$\mathbf{B}_{1},\dots,\mathbf{B}_{n}$ be nontrivial algebras in
${\mathcal{V}}$, and let $\mathbf{B}$ be a subdirect subalgebra of
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$. Furthermore, let $W$,
$\widehat{\phantom{\mathbf{B}}}$, $\widehat{\mathbf{B}}_{w}$ $(w\in W)$,
$\widehat{\mathbf{B}}$, and $\sim$ be as defined above. Then, for any tuple
$c\in\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$, the following conditions
are equivalent:

  1. (1)

$c\in\mathbf{B}$.

  2. (2)

$c$ satisfies

     * •

$c|_{I}\in\mathbf{B}|_{I}$ for all $I\subseteq[n]$ with
$|I|<\max\\{\mathsf{d},3\\}$, and

     * •

$\widehat{c}|_{U}\in\widehat{\mathbf{B}}|_{U}$ for all blocks $U\,(\subseteq
W)$ of $\sim$ of size $|U|\geq\max\\{\mathsf{d},3\\}$.

  3. (3)

$\widehat{c}|_{U}\in\widehat{\mathbf{B}}|_{U}$ for all $U\subseteq W$ such
that

     * •

$|U|<\mathsf{m}\cdot\max\\{\mathsf{d},3\\}$ where
$\mathsf{m}=\max\\{|\operatorname{Irr}(\mathbf{B}_{j})|:j\in[n]\\}$, or

     * •

$U$ is a block of $\sim$ of size
$|U|\geq\mathsf{m}\cdot\max\\{\mathsf{d},3\\}$.

######  Remark 26.

The equivalence of conditions (1) and (3) in Theorem 25 can be restated as
follows: $\widehat{\mathbf{B}}$ is the intersection of the subalgebras

$\operatorname{proj}_{U}^{-1}\bigl{(}\operatorname{proj}_{U}(\widehat{\mathbf{B}})\bigr{)}=\operatorname{proj}_{U}^{-1}\bigl{(}\widehat{\mathbf{B}}|_{U}\bigr{)}$

of $\prod_{w\in W}\widehat{\mathbf{B}}_{w}$ as $U$ runs over the subsets of
$W$ listed in (3).

######  Proof 5.1 (Proof of Theorem 25).

Since $\widehat{\phantom{\mathbf{B}}}$ and $|_{U}$ ($U\subseteq W$) are
homomorphisms, it is clear that $c\in\mathbf{B}$ implies
$\widehat{c}|_{U}\in\widehat{\mathbf{B}}|_{U}$ for all $U\subseteq W$. This
proves (1) $\Rightarrow$ (3).

For the implication (3) $\Rightarrow$ (2), assume that (3) holds. Then
$\widehat{c}|_{U}\in\widehat{\mathbf{B}}|_{U}$ for all blocks $U$ of $\sim$,
so the second statement in (2) holds. To establish the first statement, choose
$I\subseteq[n]$ such that $|I|<\max\\{\mathsf{d},3\\}$, and let
$W_{I}:=\bigcup_{j\in I}W_{j}$. Since the product of the isomorphisms
$\mathbf{B}_{j}\to\widehat{\mathbf{B}}|_{W_{j}}$,
$x_{j}\mapsto(\widehat{x}_{w})_{w\in W_{j}}$ (induced by the embeddings in
(28)) yields an isomorphism

$\prod_{j\in I}\mathbf{B}_{j}\to\prod_{j\in
I}\widehat{\mathbf{B}}|_{W_{j}}\,\Bigl{(}\leq\prod_{w\in
W_{I}}\widehat{\mathbf{B}}_{w}\Bigr{)},\quad(x_{j})_{j\in
I}\mapsto(x_{w})_{w\in W_{I}}\qquad(x_{j}\in\mathbf{B}_{j}),$

which maps $\mathbf{B}|_{I}$ onto $\widehat{\mathbf{B}}|_{W_{I}}$, we get that
$c|_{I}\in\mathbf{B}|_{I}$ holds if and only if
$\widehat{c}|_{W_{I}}\in\widehat{\mathbf{B}}|_{W_{I}}$. The latter follows
from assumption (3), because $|W_{I}|\leq\sum_{j\in I}|W_{j}|=\sum_{j\in
I}|\operatorname{Irr}(\mathbf{B}_{j})|\leq\mathsf{m}|I|$. This completes the
proof of (3) $\Rightarrow$ (2).

The remaining implication (2) $\Rightarrow$ (1) is the main statement in
Theorem 25, which we will prove now. Assume that $c\notin\mathbf{B}$, but
$c|_{I}\in\mathbf{B}|_{I}$ for all $I\subseteq[n]$ with
$|I|<\max\\{\mathsf{d},3\\}$. We have to show that
$\widehat{c}|_{U}\notin\widehat{\mathbf{B}}|_{U}$ for some block
$U\,(\subseteq W)$ of $\sim$ of size $|U|\geq\max\\{\mathsf{d},3\\}$.

Using the assumption $c\notin\mathbf{B}$ and Zorn’s Lemma, we first choose and
fix a subalgebra $\mathbf{M}$ of
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$ containing $\mathbf{B}$, which
is maximal for the property that it fails to contain $c$. Then $\mathbf{M}$ is
completely $\cap$-irreducible in the lattice of subalgebras of
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$. Let
$\\{T_{1},\dots,T_{\ell}\\}$ be a partition of $[n]$ such that
$\mathbf{M}|_{T_{i}}$ is directly indecomposable for every $i\in[\ell]$, and
$\mathbf{M}$ differs from
$\mathbf{M}|_{T_{1}}\times\dots\times\mathbf{M}|_{T_{\ell}}$ by a permutation
of variables only; we will denote this fact by
$\mathbf{M}\approx\mathbf{M}|_{T_{1}}\times\dots\times\mathbf{M}|_{T_{\ell}}$.
We must have $c|_{T}\notin\mathbf{M}|_{T}$ for at least one block $T:=T_{i}$,
because otherwise
$\mathbf{M}\approx\mathbf{M}|_{T_{1}}\times\dots\times\mathbf{M}|_{T_{\ell}}$
would imply that $c\in\mathbf{M}$, contradicting the choice of $\mathbf{M}$.
Let us fix such a $T$ for the rest of the proof. Note that $|T|>1$, because
$\mathbf{M}$ is a subdirect product of $\mathbf{B}_{1},\dots,\mathbf{B}_{n}$
(as $\mathbf{B}\leq\mathbf{M}$), so we have
$c|_{j}\in\mathbf{B}_{j}=\mathbf{M}|_{j}$ for every one-element set
$\\{j\\}\subseteq[n]$.

It follows from
$\mathbf{M}\approx\mathbf{M}|_{T_{1}}\times\dots\times\mathbf{M}|_{T_{\ell}}$
that $\mathbf{M}$ is the intersection of two subalgebras of
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$, as shown below:

$\mathbf{M}\approx\Bigl{(}\mathbf{M}|_{T}\times\prod_{j\in[n]\setminus
T}\mathbf{B}_{j}\Bigr{)}\cap\Bigl{(}\prod_{j\in
T}\mathbf{B}_{j}\times\mathbf{M}|_{[n]\setminus T}\Bigr{)}.$

Since $\mathbf{M}$ is a completely $\cap$-irreducible subalgebra of
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$, we get that
$\mathbf{M}\approx\mathbf{M}|_{T}\times\prod_{j\in[n]\setminus
T}\mathbf{B}_{j}$ or $\mathbf{M}\approx\prod_{j\in
T}\mathbf{B}_{j}\times\mathbf{M}|_{[n]\setminus T}$. The latter is impossible,
because $\mathbf{M}|_{T}\lneq\prod_{j\in T}\mathbf{B}_{j}$ (as witnessed by
$c|_{T}$). Hence, for the subalgebra $\mathbf{R}:=\mathbf{M}|_{T}$ of
$\prod_{j\in T}\mathbf{B}_{j}$ we get that
$\mathbf{M}\approx\mathbf{R}\times\prod_{j\in[n]\setminus T}\mathbf{B}_{j}$.
Furthermore, $\mathbf{R}$ is both completely $\cap$-irreducible (because
$\mathbf{M}$ is) and directly indecomposable (by construction), so
$\mathbf{R}$ is a critical subalgebra of $\prod_{j\in T}\mathbf{B}_{j}$. Our
construction also implies that $\mathbf{B}|_{T}\leq\mathbf{R}$ and
$c|_{T}\notin\mathbf{R}$. Hence, $c|_{T}\notin\mathbf{B}|_{T}$. Thus, our
assumption that $c|_{I}\in\mathbf{B}|_{I}$ holds for all $I\subseteq[n]$ with
$|I|<\max\\{\mathsf{d},3\\}$ forces that $|T|\geq\max\\{\mathsf{d},3\\}$.

Now we can apply Theorem 24 to the algebras $\mathbf{B}_{t}$ ($t\in T$) in
${\mathcal{V}}$, and the critical subalgebra $\mathbf{R}$ of $\prod_{t\in
T}\mathbf{B}_{t}$ where the number of factors in the product is
$|T|\geq\max\\{\mathsf{d},3\\}$. Since $\mathbf{R}$ is a subdirect product of
the algebras $\mathbf{B}_{t}$ ($t\in T$), the reduced representation
$\overline{\mathbf{R}}$ of $\mathbf{R}$ is the quotient algebra
$\mathbf{R}/\delta_{\mathbf{R}}$ where $\delta=\prod_{t\in T}\delta_{t}$
($\delta_{t}\in\operatorname{Con}(\mathbf{B}_{t})$) is the largest product
congruence of $\prod_{t\in T}\mathbf{B}_{t}$ for which $\mathbf{R}$ is
$\delta$-saturated. Let $\overline{\mathbf{B}}_{t}:=\mathbf{B}_{t}/\delta_{t}$
for every $t\in T$. So, the conclusions of Theorem 24 can be restated as
follows:

  1. (1)

$\overline{\mathbf{R}}\leq\prod_{t\in T}\overline{\mathbf{B}}_{t}$ is a
representation of $\overline{\mathbf{R}}$ as a subdirect product of
subdirectly irreducible algebras $\overline{\mathbf{B}}_{t}$.

  2. (6)♭

$\overline{\mathbf{B}}_{s}$ and $\overline{\mathbf{B}}_{t}$ are similar for
any $s,t\in T$.

  3. (7)

Each $\overline{\mathbf{B}}_{t}$ has abelian monolith $\mu_{t}$ $(t\in T)$.

  4. (8)

For the centralizers $\rho_{\ell}:=(0:\mu_{\ell})$ of the monoliths
$\mu_{\ell}$ $(\ell\in T)$, the image of the composite map

$\overline{\mathbf{R}}\stackrel{{\scriptstyle\operatorname{proj}_{st}}}{{\rightarrow}}\overline{\mathbf{B}}_{s}\times\overline{\mathbf{B}}_{t}\twoheadrightarrow\overline{\mathbf{B}}_{s}/\rho_{s}\times\overline{\mathbf{B}}_{t}/\rho_{t}$
(29)

is the graph of an isomorphism
$\overline{\mathbf{B}}_{s}/\rho_{s}\to\overline{\mathbf{B}}_{t}/\rho_{t}$ for
any distinct $s,t\in T$.

By conclusion (1), we have for each $t\in T$ that
$\overline{\mathbf{B}}_{t}=\mathbf{B}_{t}/\delta_{t}$ is subdirectly
irreducible, so $\delta_{t}\in\operatorname{Irr}(\mathbf{B}_{t})$ and
$(t,\delta_{t})\in W$. Hence, the algebra
$\overline{\mathbf{B}}_{t}=\mathbf{B}_{t}/\delta_{t}$ is one of the subdirect
factors of $\widehat{\mathbf{B}}$, namely,
$\overline{\mathbf{B}}_{t}=\mathbf{B}_{t}/\delta_{t}=\widehat{\mathbf{B}}_{w}$
for $w=(t,\delta_{t})$. This implies also that $\mu_{t},\rho_{t}$ are the
congruences of $\overline{\mathbf{B}}_{t}=\widehat{\mathbf{B}}_{w}$ that we
denoted earlier by $\mu_{w},\rho_{w}$.

Let $\widehat{T}:=\\{(t,\delta_{t}):t\in T\\}$. Next we want to show that any
two elements of $\widehat{T}$ are related by $\sim$. Let $s,t\in T$, and let
$v:=(s,\delta_{s})$, $w:=(t,\delta_{t})$. As we noticed in the preceding
paragraph, we have that $\overline{\mathbf{B}}_{s}=\widehat{\mathbf{B}}_{v}$,
$\mu_{s}=\mu_{v}$, $\rho_{s}=\rho_{v}$, and
$\overline{\mathbf{B}}_{t}=\widehat{\mathbf{B}}_{w}$, $\mu_{t}=\mu_{w}$,
$\rho_{t}=\rho_{w}$. If $s=t$, then $v=w$, and hence $v\sim w$ holds because
$\sim$ is reflexive. So, assume from now on that $s\not=t$. Hence $v\not=w$.
In this case, checking whether $v\sim w$ holds involves two conditions. One is
that the subdirectly irreducible algebras $\widehat{\mathbf{B}}_{v}$ and
$\widehat{\mathbf{B}}_{w}$ are similar with abelian monoliths $\mu_{v}$ and
$\mu_{w}$, which follows from conclusions (6)♭–(7). The other is that the
image of $\widehat{\mathbf{B}}|_{vw}$ under the natural map
$\varphi\colon\widehat{\mathbf{B}}_{v}\times\widehat{\mathbf{B}}_{w}\twoheadrightarrow(\widehat{\mathbf{B}}_{v}/\rho_{v})\times(\widehat{\mathbf{B}}_{w}/\rho_{w})$,
is the graph of an isomorphism
$\widehat{\mathbf{B}}_{v}/\rho_{v}\to\widehat{\mathbf{B}}_{w}/\rho_{w}$. We
will establish this property by proving that
$\widetilde{\mathbf{B}}_{vw}:=\varphi(\widehat{\mathbf{B}}|_{vw})$ is equal to
the image of $\overline{\mathbf{R}}$ under the homomorphism in (29), which is
$\varphi(\overline{\mathbf{R}}|_{st})$, because the map $\twoheadrightarrow$
in (29) is $\varphi$. Let
$\widetilde{\mathbf{R}}_{st}:=\varphi(\overline{\mathbf{R}}|_{st})$. Since
$\widehat{\mathbf{B}}|_{vw}$ is a subdirect product of
$\widehat{\mathbf{B}}_{v}$ and $\widehat{\mathbf{B}}_{w}$, we get that
$\widetilde{\mathbf{B}}_{vw}$ is a subdirect product of
$\widehat{\mathbf{B}}_{v}/\rho_{v}$ and $\widehat{\mathbf{B}}_{w}/\rho_{w}$.
By the construction of $\mathbf{R}$, we have that
$\mathbf{R}\geq\mathbf{B}|_{T}$, and $\geq$ is preserved under the natural
homomorphism

$\prod_{r\in T}\mathbf{B}_{r}\twoheadrightarrow\prod_{r\in
T}\mathbf{B}_{r}/\delta_{r}=\prod_{u\in\widehat{T}}\widehat{\mathbf{B}}_{u}.$
(30)

The images of $\mathbf{R}$ and $\mathbf{B}|_{T}$ under this homomorphism are
$\overline{\mathbf{R}}$ and $\widehat{\mathbf{B}}|_{\widehat{T}}$,
respectively, hence we conclude that
$\overline{\mathbf{R}}\geq\widehat{\mathbf{B}}|_{\widehat{T}}$. Projecting
further onto the coordinates $s,t$ in $T$, and the corresponding coordinates
$v=(s,\delta_{s})$, $w=(t,\delta_{t})$ in $\widehat{T}$, we get that
$\overline{\mathbf{R}}|_{st}\geq\widehat{\mathbf{B}}|_{vw}$. Hence, it follows
that
$\widetilde{\mathbf{R}}_{st}=\varphi(\overline{\mathbf{R}}|_{st})\geq\varphi(\widehat{\mathbf{B}}|_{vw})=\widetilde{\mathbf{B}}_{vw}$.
By conclusion (8) above, $\widetilde{\mathbf{R}}_{st}$ is the graph of an
isomorphism
$\overline{\mathbf{B}}_{s}/\rho_{s}\to\overline{\mathbf{B}}_{t}/\rho_{t}$, or
equivalently, the graph of an isomorphism
$\widehat{\mathbf{B}}_{v}/\rho_{v}\to\widehat{\mathbf{B}}_{w}/\rho_{w}$.
Combining this fact with the earlier observation that
$\widetilde{\mathbf{B}}_{vw}$ is a subdirect product of
$\widehat{\mathbf{B}}_{v}/\rho_{v}$ and $\widehat{\mathbf{B}}_{w}\rho_{w}$, we
obtain that $\widetilde{\mathbf{R}}_{st}$ and $\widetilde{\mathbf{B}}_{vw}$
must be equal. In particular, $\widetilde{\mathbf{B}}_{vw}$ is the graph of an
isomorphism
$\widehat{\mathbf{B}}_{v}/\rho_{v}\to\widehat{\mathbf{B}}_{w}/\rho_{w}$, and
hence $v\sim w$.

Our arguments in the last two paragraphs show that $\widehat{T}$ is contained
in one of the blocks $U$ of $\sim$. We have
$|U|\geq|\widehat{T}|=|T|\geq\max\\{\mathsf{d},3\\}$. It remains to verify
that $\widehat{c}|_{U}\notin\widehat{\mathbf{B}}|_{U}$.

Assume, for a contradiction, that
$\widehat{c}|_{U}\in\widehat{\mathbf{B}}|_{U}$. Then projecting further to
$\widehat{T}\subseteq U$ yields that
$\widehat{c}|_{\widehat{T}}\in\widehat{\mathbf{B}}|_{\widehat{T}}$. As we saw
earlier, $\widehat{\mathbf{B}}|_{\widehat{T}}\leq\overline{\mathbf{R}}$,
therefore we get that the tuple
$\widehat{c}|_{\widehat{T}}=(c_{r}/\delta_{r})_{r\in T}$ lies in
$\overline{\mathbf{R}}$. Hence the tuple $c|_{T}=(c_{r})_{r\in T}$ lies in the
full inverse image of $\overline{\mathbf{R}}$ under the natural homomorphism
(30). This inverse image is $\mathbf{R}$, because
$\overline{\mathbf{R}}=\mathbf{R}/\delta_{\mathbf{R}}$ with
$\delta=\prod_{r\in T}\delta_{r}$, and $\mathbf{R}$ is $\delta$-saturated in
$\prod_{r\in T}\mathbf{B}_{r}$. Thus, we obtain that $c|_{T}\in\mathbf{R}$,
which is impossible, since $\mathbf{R}$ was chosen so that
$c|_{T}\notin\mathbf{R}$. This contradiction proves that
$\widehat{c}|_{U}\notin\widehat{\mathbf{B}}|_{U}$, and completes the proof of
Theorem 25.

##  6\. Algorithms Based on Theorem 25

Throughout this section we will work under the following global assumptions.

  * •

${\mathcal{V}}$ is a variety in a finite language with a $\mathsf{d}$-cube
term ($\mathsf{d}>1$),

  * •

${\mathcal{K}}$ is a finite set of finite algebras in ${\mathcal{V}}$.

Let $a_{1},\dots,a_{k},b\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
($\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}$) be an input for
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$ where
$a_{r}=(a_{r1},\dots,a_{rn})$ ($r\in[k]$) and $b=(b_{1},\dots,b_{n})$. We call
this input _$\mathsf{d}$ -coherent_ if the following conditions are satisfied:

  1. (1)

$n\geq\max\\{\mathsf{d},3\\}$;

  2. (2)

$a_{1},\dots,a_{k}$ generate a subdirect subalgebra of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$;

  3. (3)

$\mathbf{A}_{1},\dots,\mathbf{A}_{n}$ are similar subdirectly irreducible
algebras, and each $\mathbf{A}_{\ell}$ has abelian monolith $\mu_{\ell}$;

  4. (4)

$b|_{I}$ is in the subalgebra of $\prod_{i\in I}\mathbf{A}_{i}$ generated by
$\\{a_{1}|_{I},\dots,a_{k}|_{I}\\}$ for all $I\subseteq[n]$,
$|I|<\max\\{\mathsf{d},3\\}$; and

  5. (5)

for the centralizers $\rho_{\ell}:=(0:\mu_{\ell})$ of the monoliths
$\mu_{\ell}$, the subalgebra of
$\mathbf{A}_{i}/\rho_{i}\times\mathbf{A}_{j}/\rho_{j}$ generated by
$\\{(a_{1i}/\rho_{i},a_{1j}/\rho_{j}),\dots,(a_{ki}/\rho_{i},a_{kj}/\rho_{j})\\}$
is the graph of an isomorphism
$\mathbf{A}_{i}/\rho_{i}\to\mathbf{A}_{j}/\rho_{j}$ for any distinct
$i,j\in[n]$.

We define $\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}({\mathcal{K}})$ to be the restriction of
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$ to $\mathsf{d}$-coherent
inputs.

It is clear from Definition 6 that $\mathsf{d}$-coherence for inputs of
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$ can be checked in polynomial
time.

Algorithm 7 Reduction of $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ to
$\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$

0: $b_{1},\dots,b_{k},b_{k+1}\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
with $\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}\ (n\geq\mathsf{d})$

0: Is $b_{k+1}$ in the subalgebra of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by
$b_{1},\dots,b_{k}$?

1: $\mathsf{d}^{-}:=\max(\mathsf{d}-1,2)$,

2: for $I\in\binom{[n]}{\mathsf{d}^{-}}$ do

3: generate $\mathbf{B}|_{I}$ by $b_{1}|_{I},\dots,b_{k}|_{I}$

4: return NO if $b_{k+1}|_{I}\notin\mathbf{B}|_{I}$

5: end for

6: generate $\mathbf{B}_{i}$ by $b_{1}|_{i},\dots,b_{k}|_{i}$ for $i\in[n]$

7: omit all coordinates $i$ from the input for which $|\mathbf{B}_{i}|=1$ (but
keep earlier notation)

8: return YES if $n\leq\mathsf{d}^{-}$

9: $W:=\\{(j,\sigma):j\in[n],\sigma\in\operatorname{Irr}(\mathbf{B}_{j})\\}$

10: $\widehat{\mathbf{B}}_{w}:=\mathbf{B}_{j}/\sigma$,
$\mu_{w}:=\text{monolith of }\widehat{\mathbf{B}}_{w}$,
$\rho_{w}:=(0:\mu_{w})$ for each $w=(j,\sigma)\in W$

11: $\widehat{b}_{i}:=(\widehat{b}_{iw})_{w\in W}$ where
$\widehat{b}_{iw}:=b_{i}|_{j}/\sigma$ for each $i\in[k+1]$ and $w=(j,\sigma)$

12: for distinct $v,w\in W$ do

13: generate $\widetilde{\mathbf{B}}_{vw}$ by the pairs
$(\widehat{b}_{iv}/\rho_{v},\widehat{b}_{iw}/\rho_{w})$, $i\in[k]$

14: end for

15: compute the equivalence relation $\sim$ on $W$ determined by the following
condition: for distinct $v,w\in W$,  $\qquad\quad v\sim
w\quad\Leftrightarrow\quad\begin{cases}\mu_{v}\leq\rho_{v},\
\mu_{w}\leq\rho_{w},\ \text{$\widehat{B}_{v}$ and $\widehat{B}_{w}$ are
similar, and}\\\ \text{$\widetilde{\mathbf{B}}_{vw}$ is the graph of an
isomorphism
$\widehat{\mathbf{B}}_{v}/\rho_{v}\to\widehat{\mathbf{B}}_{w}/\rho_{w}$}\end{cases}$

16: find the equivalence classes $E_{1},\dots,E_{m}$ of $\sim$ of size
$>\mathsf{d}^{-}$

17: for $\lambda=1,\dots,m$ do

18: run $\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$ with
input
$\widehat{b}_{1}|_{E_{\lambda}},\dots,\widehat{b}_{k}|_{E_{\lambda}},\widehat{b}_{k+1}|_{E_{\lambda}}\in\prod_{w\in
E_{\lambda}}\widehat{\mathbf{B}}_{w}$ to get answer
$\sf{A}\in\\{\text{YES},\text{NO}\\}$

19: return NO if $\sf{A}=\text{NO}$

20: end for

21: return YES

######  Theorem 27.

The decision problems $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ and
$\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$ are
polynomial time equivalent.

######  Proof 6.1.

By Theorem 17, $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ is polynomial
time equivalent to $\operatorname{\text{\sc
SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$. Clearly,
$\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$ is
polynomial time reducible to $\operatorname{\text{\sc
SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$, because it is a subproblem of
$\operatorname{\text{\sc SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$. Therefore
it only remains to show that Algorithm 7 reduces $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$ to $\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$ in
polynomial time.

The correctness of Algorithm 7 is based on Theorem 25. Let $\mathbf{B}$ denote
the subalgebra of $\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by
$b_{1},\dots,b_{k}$. Without loss of generality we may assume that
$n\geq\mathsf{d}$. In Steps 1–5, it is checked whether $b_{k+1}|_{I}$ is
contained in the projection $\mathbf{B}|_{I}$ of $\mathbf{B}$ for each
$I\in\binom{[n]}{\mathsf{d}^{-}}$. If not, then clearly
$b_{k+1}\notin\mathbf{B}$ and the algorithm correctly returns the answer NO in
Step 4. In Step 6 the algebras $\mathbf{B}_{i}:=\mathbf{B}|_{i}$ are computed
for every $i\in[n]$. Note that by this time, $b_{k+1}$ had passed the tests in
Step 4, which implies that $b_{k+1}|_{i}\in\mathbf{B}_{i}$ holds for every
$i\in[n]$. Therefore, when in Step 7 all coordinates with $|B_{i}|=1$ are
omitted from the input tuples (but the earlier notation is kept for
simplicity), this deletion of the trivial coordinates does no affect whether
or not $b_{k+1}\in\mathbf{B}$. It follows that by the end of Step 7 we have
that

  1. (1)

$\mathbf{B}$ is a subdirect subalgebra of
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$ where
$\mathbf{B}_{1},\dots,\mathbf{B}_{n}$ are nontrivial, and

  2. (2)

$b_{k+1}|_{I}\in\mathbf{B}|_{I}$ for all $I\in\binom{[n]}{\mathsf{d}^{-}}$.

By (1) the algebra $\mathbf{B}$ satisfies the assumptions of Theorem 25, and
(2) shows that the tuple
$c:=b_{k+1}\in\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$ satisfies the
first part of condition (2) in Theorem 25.

In Steps 9–16, Algorithm 7 computes the data needed to check whether or not
$c=b_{k+1}$ satisfies the second part of condition (2) as well. In more
detail, the algorithm computes the set $W$, the subdirectly irreducible
algebras $\widehat{\mathbf{B}}_{w}$ ($w\in W$), their congruences $\mu_{w}$
(the monolith) and $\rho_{w}=(0:\mu_{w})$, the images $\widehat{b}_{i}$ of the
input tuples $b_{i}$ ($i\in[k+1]$) under the homomorphism
$\widehat{\phantom{d}}$, and finally, the equivalence relation $\sim$ on $W$,
and its equivalence classes $E_{1},\dots,E_{m}$ of size ${}>\mathsf{d}^{-}$.
All computations follow the definitions exactly, except Step 15. We explain
now why the conditions used in Step 15 to compute $\sim$ are equivalent to the
conditions in the definition of $\sim$ (stated right before Theorem 25):

  * •

The inclusion $\mu_{w}\leq\rho_{w}$ ($w\in W$) is equivalent to the condition
that $\mu_{w}$ is abelian, because the inclusion is true if $\mu_{w}$ is
abelian, whereas $\rho_{w}=0$ (and hence the inclusion fails) if $\mu_{w}$ is
nonabelian.

  * •

As discussed in the proof of Theorem 25, $\widetilde{B}_{vw}$ is the image of
$\widehat{B}|_{vw}$ under the natural map
$\widehat{\mathbf{B}}_{v}\times\widehat{\mathbf{B}}_{w}\twoheadrightarrow(\widehat{\mathbf{B}}_{v}/\rho_{v})\times(\widehat{\mathbf{B}}_{w}/\rho_{w})$.

Since $c=b_{k+1}$ satisfies the first part of condition (2) in Theorem 25, it
follows from the equivalence of conditions (1) and (2) in Theorem 25 that
$b_{k+1}\in\mathbf{B}$ if and only if $c=b_{k+1}$ satisfies the second part of
condition (2) as well, that is,

  1. (3)

$\widehat{b}_{k+1}|_{E_{\lambda}}\in\widehat{\mathbf{B}}|_{E_{\lambda}}$ for
all $\lambda\in[m]$.

This is clearly equivalent to the condition that

  1. (3)′

$\widehat{b}_{k+1}|_{E_{\lambda}}$ belongs to the subalgebra of $\prod_{w\in
E_{\lambda}}\widehat{B}_{w}$ generated by the
tuples$\widehat{b}_{1}|_{E_{\lambda}},\dots,\widehat{b}_{k}|_{E_{\lambda}}$
for all $\lambda\in[m]$.

It follows from the construction that for each $\lambda\in[m]$,
$\widehat{b}_{1}|_{E_{\lambda}},\dots,\widehat{b}_{k}|_{E_{\lambda}},\widehat{b}_{k+1}|_{E_{\lambda}}$
is a $\mathsf{d}$-coherent input for $\operatorname{\text{\sc
SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$, so condition (3)′ can be checked
using $\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$. This is
exactly what Algorithm 7 does in Steps 17–20, and returns the correct answer:
YES if (3)′ holds (including the case when $m=0$), and NO otherwise. This
completes the proof of the correctness of Algorithm 7.

Now we show that Algorithm 6 reduces $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$ to $\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$ in
polynomial time. Clearly, Steps 1, 8, and 21 require constant time. Since each
$\mathbf{B}_{i}$ ($i\in[n]$) is a subalgebra of some member of
${\mathcal{K}}$, we have $|\mathbf{B}_{i}|\leq\mathsf{a}_{{\mathcal{K}}}$
where the constant $\mathsf{a}_{{\mathcal{K}}}$ is independent of the input.
The parameter $\mathsf{d}$ is also independent of the input, and so is
$\mathsf{s}:=\max\\{|\operatorname{Irr}(\mathbf{A})|:\mathbf{A}\in\mathbb{S}{\mathcal{K}}\\}$.
It follows that $|W|\leq n\mathsf{s}$ and that each iteration of the for loops
in Steps 2–5 and 12–14 require time $O(k)$. Hence, Steps 2–5, 6–7, 9–10, 11,
and 12–14 run in $O(kn^{\mathsf{d}^{-}})$, $O(kn)$, $O(n)$, $O(kn)$, and
$O(kn^{2})$ time, respectively.

In Step 15, to determine whether $v\sim w$ holds for a particular pair of
elements $v,w\in W$ requires constant time, because the condition only
involves data on algebras in $\mathbb{H}\mathbb{S}{\mathcal{K}}$ and on
products of two such algebras. (In particular, recall from Section 2 that
similarity of $\widehat{B}_{v}$ and $\widehat{B}_{w}$ can be checked by
looking at congruences of subalgebras of
$\widehat{B}_{v}\times\widehat{B}_{w}$.) Thus, Step 15 runs in $O(n^{2})$ time
as does Step 16. Since $E_{1},\ldots,E_{m}$ are disjoint subsets of $W$ and
$|W|\leq n\mathsf{s}$, we get that $m\leq n\mathsf{s}$ and each $E_{\lambda}$
has size $|E_{\lambda}|\leq n\mathsf{s}$. Thus, in Steps 17–20,
$\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$ has to be
run at most $O(n)$ times, and the input size of each run is $O(kn)$,
approximately the same as the size of the original input.

This proves that Algorithm 7 reduces $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$ to $\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$ in
polynomial time.

Algorithm 8 For $\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}({\mathcal{K}})$ if ${\mathcal{K}}$ is in a
residually small variety

0: $\mathsf{d}$-coherent
$a_{1},\dots,a_{k},b\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
$(\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}})$ where
$a_{i}=(a_{i1},\dots,a_{in})$ for all $i\in[k]$

0: Is $b$ in the subalgebra of $\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
generated by $a_{1},\dots,a_{k}$?

1: let $\mu_{j}$ be the monolith of $\mathbf{A}_{j}$, $\rho_{j}:=(0:\mu_{j})$
for every $j\in[n]$ and $\rho:=\rho_{1}\times\dots\times\rho_{n}$

2: reindex $a_{1},\dots,a_{k}$ so that $a_{11}/\rho_{1},\dots,a_{r1}/\rho_{1}$
are pairwise distinct and
$\\{a_{11}/\rho_{1},\dots,a_{r1}/\rho_{1}\\}=\\{a_{11}/\rho_{1},\dots,a_{k1}/\rho_{1}\\}$let
$\mathcal{O}:=\\{a_{1},\dots,a_{r}\\}$

3: generate $\mathbf{A}_{1}/\rho_{1}$ by
$a_{11}/\rho_{1},\dots,a_{r1}/\rho_{1}$, and simultaneously,

4: for each new
$a/\rho_{1}=t(a_{11}/\rho_{1},\dots,a_{r1}/\rho_{1})\in\mathbf{A}_{1}/\rho_{1}$
($t$ a term) do

5: $\mathcal{O}:=\mathcal{O}\cup\\{t(a_{1},\dots,a_{r})\\}$

6: end for

7: find the equivalence relation $\equiv$ on $[n]$ defined by  $s\equiv t\ \
\Leftrightarrow\ \ \mathbf{A}_{s}=\mathbf{A}_{t}\text{ and
}o|_{s}=o|_{t}\text{ for all $o\in\mathcal{O}$}\qquad\text{($s,t\in[n]$)}$ let
$T$ be a transversal for the blocks of $\equiv$, and let
$\mathbf{A}_{T}:=\prod_{j\in T}\mathbf{A}_{j}$

8: enumerate the elements of the subalgebra $P$ of $\mathbf{A}_{T}^{A_{T}}$
generated by the identity function $A_{T}\to A_{T}$ and by the constant
functions with value $o|_{T}$ ($o\in\mathcal{O}$) (so every $p\in P$ is of the
form $A_{T}\to A_{T},(x_{t})_{t\in T}\mapsto(p_{t}(x_{t}))_{t\in T}$ for some
function $p_{t}\colon A_{t}\to A_{t}$)

9: find $o\in\mathcal{O}$ such that $b\in o/\rho$

10: $H:=\emptyset$

11: for $p\in P$ do

12: for $c\in\\{a_{1},\dots,a_{k}\\}$ do

13: for $j\in[n]$ do

14: find $t\in T$ with $t\equiv j$

15: let $d_{j}:=p_{t}(c|_{j})$

16: end for

17: $d:=(d_{1},\dots,d_{n})$

18: if $d\in o/\rho$ then

19: $H:=H\cup\\{d\\}$

20: end if

21: end for

22: end for

23: run Sims’ algorithm for $\operatorname{\text{\sc SMP}}(\mathcal{G})$ with
the input $H\cup\\{b\\}\subseteq\mathbf{G}_{1}\times\dots\times\mathbf{G}_{n}$
to check whether $b\in\langle H\rangle$ where $\mathbf{G}_{j}$ is the group
$(o_{j}/\rho_{j};+_{o_{j}},-_{o_{j}},o_{j})$ for each $j\in[n]$ and
$\mathcal{G}$ is the family of all induced abelian groups on blocks of abelian
congruences of algebras in $\mathcal{K}$; get answer
$\sf{A}\in\\{\text{YES},\text{NO}\\}$

24: return $\sf{A}$

######  Theorem 28.

If, in addition to Assumption 6, the variety ${\mathcal{V}}$ is residually
small, then

$\operatorname{\text{\sc SMP}}({\mathcal{K}})\in\mathsf{P}.$

######  Proof 6.2.

By Theorem 27, $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ is polynomial
time equivalent to $\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$. Also, if
${\mathcal{K}}$ is finite, so is $\mathbb{H}\mathbb{S}{\mathcal{K}}$.
Therefore it suffices to prove that $\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}({\mathcal{K}})\in\mathsf{P}$ holds for every
${\mathcal{K}}$ as in the theorem. We will prove this by showing that, under
the assumptions of the theorem, Algorithm 8 solves
$\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}({\mathcal{K}})$ in polynomial time.

First we discuss the correctness of Algorithm 8. Let
$a_{1},\dots,a_{k},b\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
($\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}$) be a correct input for
$\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}({\mathcal{K}})$ (i.e., a
$\mathsf{d}$-coherent input for $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$). Then conditions (1)–(5) in Definition 6 hold. By
condition (3), the algebras $\mathbf{A}_{j}$ ($j\in[n]$) are subdirectly
irreducible with abelian monoliths, so in Step 1 of Algorithm 8 the monoliths
$\mu_{j}$ and their centralizers $\rho_{j}$ will be found. Moreover, since
${\mathcal{K}}$ is assumed to be in a residually small variety, we get from
Theorem 1(2) and Corollary 2 that

$\rho_{j}\text{ is an abelian congruence of }\mathbf{A}_{j}\text{ for every
}j\in[n].$ (31)

Let $\mathbf{B}$ denote the subalgebra of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by the input tuples
$a_{1},\dots,a_{k}$, and let $\rho$ denote the product congruence
$\rho_{1}\times\dots\times\rho_{n}$ on
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$. The restriction of $\rho$ to
$\mathbf{B}$ will be denoted by $\rho_{\mathbf{B}}$. Condition (5) in
Definition 6 implies that

$\text{the map
}\mathbf{B}/\rho_{\mathbf{B}}\to\mathbf{A}_{j}/\rho_{j},(x_{1},\dots,x_{n})/\rho_{\mathbf{B}}\mapsto
x_{j}/\rho_{j}\text{ is a bijection for every }j\in[n].$ (32)

Finally, conditions (1) and (4) together imply that for the input tuple $b$ we
have $b|_{I}\in\mathbf{B}|_{I}$ for all sets $I\in\binom{[n]}{2}$. Hence, we
have
$b|_{i,j}/(\rho_{i}\times\rho_{j})\in\mathbf{B}|_{i,j}/(\rho_{i}\times\rho_{j})$
for all $i,j\in[n]$. Since, by condition (5),
$\mathbf{B}|_{i,j}/(\rho_{i}\times\rho_{j})$ is the graph of an isomorphism
$\mathbf{A}_{i}/\rho_{i}\to\mathbf{A}_{j}/\rho_{j}$ for every pair $i,j\in[n]$
($i\neq j$), it follows that the tuple
$b/\rho=(b|_{1}/\rho_{1},\dots,b|_{n}/\rho_{n})$ belongs to
$\mathbf{B}[\rho]/\rho$. Hence,

$b\text{ is an element of the algebra }\mathbf{B}[\rho],\text{ the
}\rho\text{-saturation of }\mathbf{B}.$ (33)

We return to the analysis of Algorithm 8. After appropriately reindexing
$a_{1},\dots,a_{k}$, Steps 2–6 produce a subset $\mathcal{O}$ of $\mathbf{B}$
such that the first coordinates of the tuples in $\mathcal{O}$ form a
transversal for the $\rho_{1}$-classes of $\mathbf{A}_{1}$. Thus, it follows
from (32) that the tuples in $\mathcal{O}$ form a transversal for the
$\rho_{\mathbf{B}}$-classes of $\mathbf{B}$, and hence also for the
$\rho$-classes of $\mathbf{B}[\rho]$. Let $|\mathcal{O}|=\ell$. Since
$|\mathcal{O}|=\bigl{|}\mathcal{O}|_{1}\bigr{|}$, we have
$\ell=|{\mathbf{A}}_{1}/\rho_{1}|<|A_{1}|$.

Now let $\equiv$, $T$, and $\mathbf{A}_{T}$ be as defined (and computed) in
Step 7, and let $\mathbf{A}:=\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$.
During our discussion of Steps 8–24 we will use computations where the same
term is used in different algebras. To make it easier for the reader to keep
track of where each computation takes place, we will use superscripts to
indicate the relevant algebras.

It is easy to see that the set $P$ of functions $A_{T}\to A_{T}$ computed in
Step 8 is

$P=\\{\mathsf{t}^{{\mathbf{A}}_{T}}(x,\mathcal{O}|_{T}):\text{$\mathsf{t}$ is
a $(1+\ell)$-ary term}\\}$ (34)

where we assume that an ordering of $\mathcal{O}$ has been fixed to ensure
that its elements are always substituted into terms in that fixed order. Our
observation (33) shows that in Step 9 Algorithm 8 will find an element
$o\in\mathcal{O}$ such that $b\in o/\rho$.

The set $H$ obtained by Algorithm 8 after completing Steps 10–22 is

$H=\\{\mathsf{t}^{\mathbf{A}}(a_{i},\mathcal{O})\in o/\rho:i\in[k],\
\text{$\mathsf{t}$ is a $(1+\ell)$-ary term}\\}.$ (35)

######  Proof 6.3 (Proof of Claim 6.2.).

We will use the notation from Steps 10–22. Let $p\in P$ and
$c\in\\{a_{1},\dots,a_{k}\\}$, say $c=(c_{1},\dots,c_{n})$. By (34), $p\in P$
if and only if $p$ is a unary polynomial operation of $\mathbf{A}_{T}$ of the
form $\mathsf{t}^{{\mathbf{A}}_{T}}(x,\mathcal{O}|_{T})$ for some
$(1+\ell)$-ary term $\mathsf{t}$. Our goal is to show that for every choice of
$p$ and $c$ the tuple $d$ computed in Steps 13–17 is

$d=\mathsf{t}^{\mathbf{A}}(c,\mathcal{O}).$ (36)

This will prove that the tuples $d$ computed in Steps 13–17 are exactly the
elements of $\mathbf{A}$ of the form $\mathsf{t}^{\mathbf{A}}(c,\mathcal{O})$
where $c\in\\{a_{1},\dots,a_{k}\\}$ and $\mathsf{t}$ is a $(1+\ell)$-ary term.
Since such a tuple $d$ is added to $H$ in Steps 18–20 if and only if $d$ also
satisfies $d\in o/\rho$, the equality (35) will follow.

To verify (36) let $j\in[n]$ and let $t\in T$ be the unique transversal
element such that $t\equiv j$. By the definition of $\equiv$ we have that
$o^{\prime}|_{t}=o^{\prime}|_{j}$ for all $o^{\prime}\in\mathcal{O}$. The
latter condition may be written as $\mathcal{O}|_{t}=\mathcal{O}|_{j}$ (with
the fixed ordering of $\mathcal{O}$ in mind, these are tuples of elements in
$\mathbf{A}_{t}=\mathbf{A}_{j}$). The function
$p_{t}\colon\mathbf{A}_{t}\to\mathbf{A}_{t}$ computed in Step 8 is the
polynomial function $\mathsf{t}^{{\mathbf{A}}_{t}}(x,\mathcal{O}|_{t})$ of
$\mathbf{A}_{t}$. Thus, using the equalities $\mathbf{A}_{t}=\mathbf{A}_{j}$
and $\mathcal{O}|_{t}=\mathcal{O}|_{j}$ we get that

$d_{j}=p_{t}(c_{j})=\mathsf{t}^{{\mathbf{A}}_{t}}(c_{j},\mathcal{O}|_{t})=\mathsf{t}^{{\mathbf{A}}_{j}}(c_{j},\mathcal{O}|_{j})=\mathsf{t}^{\mathbf{A}}(c,\mathcal{O})|_{j}.$

This holds for every $j\in[n]$, so the proof of (36), and hence the proof of
Claim 6.2, is complete.

To establish the correctness of the last two steps of Algorithm 8 recall from
(31) that $\rho_{j}$ is an abelian congruence of $\mathbf{A}_{j}$ for every
$j\in[n]$. Therefore, $\rho=\rho_{1}\times\dots\times\rho_{n}$ is an abelian
congruence of $\mathbf{A}=\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$.
Hence, by Theorem 2.3 (1), there is an induced abelian group
$\mathbf{G}:=(o/\rho;+_{0},-_{o},o)$ on the $\rho$-class $o/\rho$. Moreover,
since $\rho$ is the product congruence $\rho_{1}\times\dots\times\rho_{n}$ of
$\mathbf{A}$, we get that
$\mathbf{G}=\mathbf{G}_{1}\times\dots\times\mathbf{G}_{n}$ where
$\mathbf{G}_{j}$ is the group $(o_{j}/\rho_{j};+_{o_{j}},-_{o_{j}},o_{j})$ for
every $j\in[n]$. Recall also that $b\in o/\rho$, that is, $b$ is contained in
$\mathbf{G}=\mathbf{G}_{1}\times\dots\times\mathbf{G}_{n}$.

The following conditions on $b$ are equivalent:

  1. (1)

$b$ is in the subalgebra $\mathbf{B}$ of
$\mathbf{A}=\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by
$\\{a_{1},\dots,a_{k}\\}$;

  2. (2)

$b$ is in the subgroup of
$\mathbf{G}=\mathbf{G}_{1}\times\dots\times\mathbf{G}_{n}$ generated by the
set $H$.

######  Proof 6.4 (Proof of Claim 6.2.).

To prove the implication (1) $\Rightarrow$ (2) assume that $b\in\mathbf{B}$,
that is, $b=g(a_{1},\dots,a_{k})$ for some $k$-ary term $g$. For each
$i\in[k]$, let $o^{(i)}$ denote the unique element of $\mathcal{O}$ in the
$\rho_{\mathbf{B}}$-class of $a_{i}$. Since $g(a_{1},\dots,a_{k})=b\in
o/\rho$, it follows from Theorem 2.3 (2) that

$g(a_{1},\dots,a_{k})=g(a_{1},o^{(2)}\dots,o^{(k)})+_{o}g(o^{(1)},a_{2},o^{(3)}\dots,o^{(k)})+_{o}\dots{\\\
}+_{o}g(o^{(1)},\dots,o^{(k-1)},a_{k})-_{o}(k-1)g(o^{(1)},\dots,o^{(k-1)},o^{(k)}).$

All $+_{o}$-summands on the right hand side belong to $H$, therefore $b$ is in
the subgroup of $\mathbf{G}=\mathbf{G}_{1}\times\dots\times\mathbf{G}_{n}$
generated by $H$.

For the reverse implication (2) $\Rightarrow$ (1) notice first that
$H\subseteq B$, because $\mathbf{B}$ is a subalgebra of
$\mathbf{A}=\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ and the elements of
$H$ are obtained from $a_{1},\dots,a_{k}\in B$ by unary polynomial operations
of $\mathbf{A}$ that are constructed from term operations by using parameters
from $\mathcal{O}\subseteq B$ only. Since the group operations $+_{o}$,
$-_{o}$, $o$ of $\mathbf{G}$ are also polynomial operations of $\mathbf{A}$
obtained from term operations using parameters from $\mathcal{O}$ only, we get
that the subgroup of $\mathbf{G}$ generated by $H$ is contained in
$\mathbf{B}$.

As in Step 23 of Algorithm 8, let ${\mathcal{G}}$ denote the set of all
induced abelian groups on blocks of abelian congruences of algebras in
${\mathcal{K}}$. Then, clearly,
$\mathbf{G}_{1},\dots,\mathbf{G}_{n}\in{\mathcal{G}}$. Therefore, Claim 6.2
shows that $\operatorname{\operatorname{\text{\sc
SMP}}_{\text{$\mathsf{d}$-coh}}}({\mathcal{K}})$ run with the input
$a_{1},\dots,a_{k},b$ in $\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
($\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}$) has the same answer as
$\operatorname{\text{\sc SMP}}({\mathcal{G}})$ run with the input $H$ and $b$
in $\mathbf{G}_{1}\times\dots\times\mathbf{G}_{n}$
($\mathbf{G}_{1},\dots,\mathbf{G}_{n}\in{\mathcal{G}}$). Hence, Algorithm 8
finds the correct answer in Steps 23, 24. The proof of the correctness of
Algorithm 8 is complete.

To prove that Algorithm 8 runs in polynomial time, we will estimate the time
complexity of each step separately. Recall that $\mathsf{a}_{{\mathcal{K}}}$
denotes the maximum size of an algebra in ${\mathcal{K}}$.

Steps 1 and 3–6 run in $O(n)$ time, while Step 2 runs in $O(kn)$ time. In Step
7, $\equiv$ and a transversal $T$ for the blocks of $\equiv$ can be found in
$O(n^{2})$ time, since $\ell=|\mathcal{O}|$ is bounded above by a constant
($<|A_{1}|\leq\mathsf{a}_{{\mathcal{K}}}$) which is independent of the size of
the input. Since $\equiv$ is the kernel of the map
$[n]\to{\mathcal{K}}\times\bigcup_{i\in[n]}A_{i}^{\ell}$,
$j\mapsto(\mathbf{A}_{j},\mathcal{O}|_{j})$, the number $|T|$ of the
$\equiv$-blocks is at most $|{\mathcal{K}}|\mathsf{a}_{{\mathcal{K}}}^{\ell}$,
independent of the input. Therefore, $\mathbf{A}_{T}$ can be computed in
constant time, and Step 7 altogether requires $O(n^{2})$ time. For the same
reason, $|\mathbf{A}_{T}^{A_{T}}|$ is also bounded above by a constant,
independent of the input, therefore Step 8 runs in constant time. Step 9 also
runs in constant time, because, in view of (32), $b\in o/\rho$ is equivalent
to $b|_{1}\in o|_{1}/\rho_{1}$. Clearly, Step 10 also runs in constant time.

Using the previous estimates on $|P|\,(\leq|\mathbf{A}_{T}^{A_{T}}|)$ and
$|T|$ we see that the number of iterations of the outer for loop (line 11) is
bounded above by a constant, while the inner for loops starting in Step 12 and
Step 13 iterate $k$ and $n$ times, respectively. In each iteration, Steps
14–15 and 18–20 require constant time. Thus Steps 11–22 run in $O(kn)$ time.

In Steps 11–22 at most one element is added to $H$ for each choice of $p\in P$
and $c\in\\{a_{1},\dots,a_{k}\\}$. Since $|P|$ is bounded above by a constant
independent of the input, we get that $|H|$ has size $O(k)$. Thus, in Step 23
the size of the input $H\cup\\{b\\}$ for $\operatorname{\text{\sc
SMP}}({\mathcal{G}})$ is $O(kn)$. Moreover, the size of each group in
${\mathcal{G}}$ is $\leq\mathsf{a}_{{\mathcal{K}}}$. Since Sims’ algorithm for
$\operatorname{\text{\sc SMP}}({\mathcal{G}})$ runs in $O(kn^{3})$ time [28,
Corollary 3.7] on an input
$H\cup\\{b\\}\subseteq\mathbf{G}_{1}\times\dots\times\mathbf{G}_{n}$ with
$|H|=O(k)$, we get that Step 23 of Algorithm 8 requires $O(kn^{3})$ time.
Clearly, Step 24 runs in constant time.

Combining the time complexities of Steps 1–24 we get that Algorithm 8 runs in
$O(kn^{3})$ time. This completes the proof of Theorem 28.

### Acknowledgement.

The authors are thankful to the anonymous referees for their careful reading
and suggestions.

## References

  * [1] K. A. Baker and A. F. Pixley.  Polynomial interpolation and the Chinese remainder theorem for algebraic systems.  Math. Z., 143(2):165–174, 1975.
  * [2] G. Baumslag, C. F. Miller, III, and H. Short.  Unsolvable problems about small cancellation and word hyperbolic groups.  Bull. London Math. Soc., 26(1):97–101, 1994.
  * [3] J. Berman, P. Idziak, P. Marković, R. McKenzie, M. Valeriote, and R. Willard.  Varieties with few subalgebras of powers.  Trans. Amer. Math. Soc., 362(3):1445–1473, 2010.
  * [4] A. Bulatov, H. Chen, and V. Dalmau.  Learning intersection-closed classes with signatures.  Theoret. Comput. Sci., 382(3):209–220, 2007.
  * [5] A. Bulatov and V. Dalmau.  A simple algorithm for Mal′tsev constraints.  SIAM J. Comput., 36(1):16–27 (electronic), 2006.
  * [6] A. Bulatov, M. Kozik, P. Mayr, and M. Steindl.  The subpower membership problem for semigroups.  Internat. J. Algebra Comput., 26(7):1435–1451, 2016.
  * [7] S. Burris and H. P. Sankappanavar.  A course in universal algebra.  Springer New York Heidelberg Berlin, 1981.
Available from `https://www.math.uwaterloo.ca/~snburris/htdocs/UALG/univ-
algebra2012.pdf`.

  * [8] V. Dalmau and P. Jeavons.  Learnability of quantified formulas.  Theoret. Comput. Sci., 306(1-3):485–511, 2003.
  * [9] T. Dent, K. Kearnes, and Á. Szendrei.  An easy test for congruence modularity.  Algebra Universalis, 67(4):375–392, 2012.
  * [10] M. Dyer and D. Richerby.  An effective dichotomy for the counting constraint satisfaction problem.  SIAM J. Comput., 42(3):1245–1274, 2013.
  * [11] R. Freese and R. McKenzie.  Commutator Theory for Congruence Modular Varieties, volume 125 of London Math. Soc. Lecture Note Ser. Cambridge University Press, 1987.  Available from `http://math.hawaii.edu/~ralph/Commutator/comm.pdf`.
  * [12] R. Freese and R. McKenzie.  Residually small varieties with modular congruence lattices.  Trans. Amer. Math. Soc., 264(2):419–430, 1981.
  * [13] M. Furst, J. Hopcroft, and E. Luks.  Polynomial-time algorithms for permutation groups.  In 21st Annual Symposium on Foundations of Computer Science (Syracuse, N.Y., 1980), pages 36–41. IEEE, New York, 1980.
  * [14] R. I. Grigorchuk and J. S. Wilson.  A structural property concerning abstract commensurability of subgroups.  J. London Math. Soc. (2), 68(3):671–682, 2003.
  * [15] P. Idziak, P. Marković, R. McKenzie, M. Valeriote, and R. Willard.  Tractability and learnability arising from algebras with few subpowers.  SIAM J. Comput., 39(7):3023–3037, 2010.
  * [16] K. A. Kearnes and Á. Szendrei.  Clones of algebras with parallelogram terms.  Internat. J. Algebra Comput., 22(1), 2012.
  * [17] D. Knuth.  Efficient representation of perm groups.  Combinatorica, 11(1):33–43, 1991.
  * [18] D. Kozen.  Complexity of finitely presented algebras.  In Ninth Annual ACM Symposium on Theory of Computing (Boulder, Colo., 1977), pages 164–177, 1977.
  * [19] D. Kozen.  Lower bounds for natural proof systems.  In 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977), pages 254–266. IEEE Comput. Sci., Long Beach, Calif., 1977.
  * [20] M. Kozik.  A finite set of functions with an EXPTIME-complete composition problem.  Theoret. Comput. Sci., 407(1-3):330–341, 2008.
  * [21] J. S. Leon.  On an algorithm for finding a base and a strong generating set for a group given by generating permutations.  Math. Comp., 35(151):941–974, 1980.
  * [22] P. Mayr.  The subpower membership problem for Mal’cev algebras.  International Journal of Algebra and Computation (IJAC), 22(7), 2012\.
  * [23] V. Shpilrain and A. Ushakov.  Thompson’s group and public key cryptography, volume 3531 of LNCS.  2005\.
  * [24] V. Shpilrain and G. Zapata.  Using the subgroup membership search problem in public key cryptography.  In Algebraic methods in cryptography, volume 418 of Contemp. Math., pages 169–178. Amer. Math. Soc., Providence, RI, 2006.
  * [25] C. Sims.  Computational methods in the study of permutation groups.  In J. Leech, editor, Computational problems in abstract algebra, Conf. Oxford, pages 169–183, 1970.
  * [26] M. Steindl.  The subpower membership problem for bands.  J. Algebra, 489:529–551, 2017.
  * [27] R. Willard.  Four unsolved problems in congruence permutable varieties.  Talk at the ”Conference on Order, Algebra, and Logics”, Nashville, 2007\.
  * [28] S. Zweckinger.  Computing in direct powers of expanded groups, Master’s Thesis, JKU Linz, Austria, 2015.


# Observations of GRB 230307A by TESS

Michael M. Fausnaugh Department of Physics and Kavli Institute for
Astrophysics and Space Research, Massachusetts Institute of Technology,
Cambridge, MA 02139, USA Michael M. Fausnaugh<EMAIL_ADDRESS>Rahul Jayaraman
Department of Physics and Kavli Institute for Astrophysics and Space Research,
Massachusetts Institute of Technology, Cambridge, MA 02139, USA  Roland
Vanderspek  Department of Physics and Kavli Institute for Astrophysics and
Space Research, Massachusetts Institute of Technology, Cambridge, MA 02139,
USA  George R. Ricker  Department of Physics and Kavli Institute for
Astrophysics and Space Research, Massachusetts Institute of Technology,
Cambridge, MA 02139, USA  Christopher J. Burke Department of Physics and Kavli
Institute for Astrophysics and Space Research, Massachusetts Institute of
Technology, Cambridge, MA 02139, USA  Knicole D. Colón NASA Goddard Space
Flight Center, 8800 Greenbelt Rd, Greenbelt, MD 20771, USA  Scott W. Fleming
Space Telescope Science Institute, 3700 San Martin Dr, Baltimore, MD 21218,
USA  Hannah M. Lewis Space Telescope Science Institute, 3700 San Martin Dr,
Baltimore, MD 21218, USA  Susan Mullally Space Telescope Science Institute,
3700 San Martin Dr, Baltimore, MD 21218, USA  Allison Youngblood NASA Goddard
Space Flight Center, 8800 Greenbelt Rd, Greenbelt, MD 20771, USA  Thomas
Barclay University of Maryland, Baltimore County, 1000 Hilltop Circle,
Baltimore, MD 21250, USA  NASA Goddard Space Flight Center, 8800 Greenbelt Rd,
Greenbelt, MD 20771, USA  Eric Burns Department of Physics and Astronomy,
Louisiana State University, Baton Rouge, LA 70803 USA  David W. Latham  Center
for Astrophysics — Harvard & Smithsonian, 60 Garden Street, Cambridge, MA
02138  S. Seager Department of Physics and Kavli Institute for Astrophysics
and Space Research, Massachusetts Institute of Technology, Cambridge, MA
02139, USA  Department of Earth, Atmospheric, and Planetary Sciences,
Massachusetts Institute of Technology, Cambridge, MA 02139, USA  Department of
Aeronautics and Astronautics, MIT, 77 Massachusetts Avenue, Cambridge, MA
02139, USA  Joshua N. Winn Department of Astrophysical Sciences, Princeton
University, 4 Ivy Lane, Princeton, NJ 08544, USA  Jon M. Jenkins  NASA Ames
Research Center, Moffett Field, CA, 94035, USA

###### Abstract

We present the TESS light curve of GRB 230307A. We find two distinct
components: a bright, prompt optical component at the time of the Fermi
observation that peaked at TESS magnitude $14.49\pm 0.05$ (averaged over 200
seconds), followed by a gradual rise and fall over 0.5 days, likely associated
with the afterglow, that peaked at $17.65\pm 0.06$ mag. The prompt component
is observed in a single 200s Full Frame Image and was undetectable in the next
TESS image ($T_{\rm mag}>17.79$). Assuming that the onset of the optical
transient was coincident with the gamma-ray emission, the prompt emission
lasted less than 73.6 seconds, which implies the true peak was actually
brighter than $T_{\rm mag}=$ 13.40. We also fit parametric models to the
afterglow to characterize its shape. The TESS TICA light curve can be
retrieved at
https://tess.mit.edu/public/tesstransients/light_curves/lc_grb230307A_cleaned.txt.

GRB 230307A

††software:  Matplotlib (Hunter, 2007), Numpy (van der Walt et al., 2011),
Scipy (Oliphant, 2007), Astropy (Astropy Collaboration et al., 2018),
Astroquery (Ginsburg et al., 2019), gwcs (Dencheva et al., 2020), TICA
(Fausnaugh et al., 2020)

##  1 Introduction

GRB 230307A was a long gamma-ray burst discovered by Fermi at
BJD$-2,460,000$=11.15549 days (15:44:06 UT on 2023 March 7, GCN33405; Fermi
GBM Team at MSFC/Fermi-GBM 2023). A fading optical afterglow was observed 9–56
hours after the GRB trigger by ULTRACAM (Levan et al. 2023), GMOS-S on Gemini
South (O’Connor et al. 2023), RASA36, and KMTnet (Im et al. 2023). The
coordinates reported by Levan et al. (2023) are RA = 04:03:25.83, Dec =
$-$75:22:42.7.

The Transiting Exoplanet Survey Satellite (TESS, Ricker et al. 2015) observed
the optical afterglow of GRB 230307A in the Full Frame Images (FFIs), sampled
at 200 seconds. In this research note, we present the TESS light curve and
observed properties of the optical emission.

##  2 Observations and Data Reduction

TESS observed GRB 230307A as part of its normal operations in Sector 62, which
lasted from 2023 February 12 to March 10. The FFI data from March 3–10 were
downloaded from the spacecraft on 2023 March 10, processed by the Payload
Operations Center (POC) at MIT, and delivered to the Mikulski Archive for
Space Telescopes (MAST) as a TICA High Level Science Product,
https://doi.org/10.17909/t9-9j8c-7d30 (catalog doi:10.17909/t9-9j8c-7d30)
(Fausnaugh et al., 2020).111https://archive.stsci.edu/hlsp/tica The order of
processing events was

  * •

March 10, 16:23 UTC—Deep Space Network (DSN) begins contact with the TESS
spacecraft to downlink the data.

  * •

March 11, 10:56 UTC—Compressed data arrive at POC from the DSN; POC begins
decoding data delivery and writing image files.

  * •

March 11, 16:35 UTC—POC begins calibrating data and fitting World Coordinate
Solutions as part of the TICA data delivery.

  * •

March 11, 18:42 UTC—POC begins staging and verifying the TICA delivery to
MAST.

  * •

March 12, 1:50 UTC—MAST begins data ingest.

  * •

March 12, 6:40 UTC—GRB data are made public on MAST, announced on the MAST
holdings
page,222https://outerspace.stsci.edu/display/TESS/TESS+Holdings+Available+by+MAST+Service
and announced on MAST social media.

Once the data were public, we processed the images with the difference imaging
analysis pipeline described by Fausnaugh et al. (2021).

We identified a transient point source in the TESS difference image
overlapping with the Fermi trigger at BJD$-2,460,000$=11.15518 days, close to
the coordinates reported by Levan et al. (2023). We measured the position of
the source using flux-weighted centroids in a 5x5 square pixel aperture. We
found a position of RA = 04:03:25.36, Dec = $-$75:22:41.31, which agrees with
the position from ULTRACAM to 1.8 arcseconds. This difference is consistent
with the typical 1$\sigma$ precision of TICA World Coordinate Solutions, about
2 arcseconds.

We extracted light curves from the difference images using forced PSF
photometry at the location of the afterglow reported by Levan et al. (2023).
Figure 1 shows the resulting light curve. Based on the scatter of the light
curve prior to the GRB discovery, we estimate a 5$\sigma$ limiting magnitude
of 18.63 in 1600 seconds. The TESS light curve is available at
https://tess.mit.edu/public/tesstransients/light_curves/lc_grb230307A_cleaned.txt.
Information on the file format and processing steps is available on the same
website.333https://tess.mit.edu/public/tesstransients/pages/readme.html

The light curve shows two distinct components. First is a prompt rise from
zero flux to TESS mag $T_{\rm mag}=$ $14.49\pm 0.05$ in a single FFI at
BJD$-2,460,000$ $=11.15518$ days (mid exposure). The quoted uncertainty
includes a statistical uncertainty of 0.02 mag, but is dominated by
uncertainty in the TESS instrument absolute flux calibration (Vanderspek et
al., 2018). The source is not detected in the next FFI, with a 3$\sigma$ upper
limit of 17.79 mag. The second emission component starts just after the prompt
emission, and consists of a gradual rise and fall in the TESS light curve over
0.5 days, likely associated with the afterglow.

Figure 1: TESS light curve of GRB 230307A. The large star shows the prompt
emission coincident with the Fermi discovery at BJD$-2,460,000$=11.15549 days
(vertical red line). The grey marks show the 200 second cadence light curve,
and the black points show the light curve binned to 1600 seconds. The limiting
magnitude in 1600 seconds is 18.63, based on the scatter of the light curve
prior to the GRB discovery. All timestamps are given relative to 2,460,000
BJD. Fits for two models of the afterglow are shown: a double power law (PL)
and a fast-rise exponential-decay (FRED) model. For both fits, we excluded the
prompt emission at the time of the Fermi trigger. Models were fit to the
original light curve sampled at 200 seconds—data are binned here only for
display purposes. The horizontal dashed line shows the residual background of
the FRED model, which is a nuisance parameter in our fits. The vertical blue
line shows the break time $t_{\rm break}$ of the double power law. The TESS
light curve is available at
https://tess.mit.edu/public/tesstransients/light_curves/lc_grb230307A_cleaned.txt.

##  3 Analysis of the Afterglow

We fit two parametric models to the afterglow light curve, a fast-rise
exponential-decay (FRED) model and a double power law model. We fit the
original data sampled at 200 seconds. We excluded the prompt emission at
$T_{\rm mag}=14.49$ from the fits to the afterglow emission. The reported
uncertainties correspond to the 68% confidence intervals of the fits. For both
models, we fit a residual background error as a nuisance parameter, which is
consistent with zero at $1\sigma$.

From the FRED model, we find that

  * •

the peak magnitude of the afterglow is $17.65\pm 0.06$,

  * •

the rise-time $t_{\rm rise}=$ $0.057\pm 0.007$ days,

  * •

the time containing 90% of the flux $t_{90}=$ $0.5\pm 0.1$ days,

  * •

and the exponential decay timescale $t_{\rm exp}=$ $0.23\pm 0.03$ days.

For the double power law model, we used the parameterization of Li et al.
(2012):

$\displaystyle F=F_{02}\left[\left(\frac{t}{t_{\rm
break}}\right)^{\alpha_{1}\omega}+\left(\frac{t}{t_{\rm
break}}\right)^{\alpha_{2}\omega}\right]^{-1/\omega}$ (1)

where $F_{02}$ is the flux normalization at the break time $t_{\rm break}$,
while $\alpha_{1}$, and $\alpha_{2}$ are slope parameters. We fixed the
smoothing parameter $\omega$ to a value of 5.0. The best-fit model yields

  * •

$t_{\rm break}=$ $0.09\pm 0.02$ days after the Fermi trigger,

  * •

$\alpha_{1}=$ $0.6\pm 0.2$,

  * •

and $\alpha_{2}=$ $-0.21\pm 0.07$.

We also fit the TESS light curve with the deep $r$-band magnitudes reported by
Levan et al. (2023) and O’Connor et al. (2023), and found consistent results.

##  4 Discussion

The end time of the FFI with the prompt emission is BJD$-2,460,000$=11.15634
days, while the Fermi trigger is at BJD$-2,460,000$=11.15549 days. Assuming
that the onset of the optical light curve is coincident with the onset of the
gamma-ray emission observed by Fermi, the prompt emission observed by TESS
lasted less than 73.6 seconds. A shorter duration implies a higher peak
magnitude for the same fluence; we find $T_{\rm mag}=$13.40 mag for a 73.6
second burst, and the peak could be even brighter if the duration of the
prompt emission is shorter. For a given luminosity distance $D$, the isotropic
monochromatic luminosity at $7839$ Å (the pivot wavelength of the TESS filter)
would be greater than $9\times 10^{44}(D/1\,\,{\rm Gpc})^{2}$ erg s-1. This
calculation is corrected for Galactic extinction at $7839$ Å assuming a
Cardelli, Clayton, & Mathis 1989 extinction law and $E(B-V)=0.0758$ mag from
Schlafly & Finkbeiner 2011, but does not take into account the unknown
spectral shape of the GRB in the broad TESS filter (6,000–10,000 Å).

These data demonstrate the utility of wide-field, continuous monitoring for
studies of fast extragalactic transients. TESS data released approximately
every 7 days as TICA High Level Science Products will facilitate these studies
over the next several years.

## acknowledgments

We thank the TESS-POC team at MIT and MAST for facilitating the TICA HLSP
delivery. The TESS mission is funded by NASA’s Science Mission directorate.

## References

  * Astropy Collaboration et al. (2018) Astropy Collaboration, Price-Whelan, A. M., Sipőcz, B. M., et al. 2018, AJ, 156, 123
  * Cardelli et al. (1989) Cardelli, J. A., Clayton, G. C., & Mathis, J. S. 1989, ApJ, 345, 245
  * Dencheva et al. (2020) Dencheva, N., Mumford, S., Bradley, L., et al. 2020, spacetelescope/gwcs: GWCS 0.15.0, doi:10.5281/zenodo.4271727
  * Fausnaugh et al. (2020) Fausnaugh, M. M., Burke, C. J., Ricker, G. R., & Vanderspek, R. 2020, Research Notes of the American Astronomical Society, 4, 251
  * Fausnaugh et al. (2021) Fausnaugh, M. M., Vallely, P. J., Kochanek, C. S., et al. 2021, ApJ, 908, 51
  * Fermi GBM Team at MSFC/Fermi-GBM (2023) Fermi GBM Team at MSFC/Fermi-GBM. 2023, GRB Coordinates Network, 33405, 1
  * Ginsburg et al. (2019) Ginsburg, A., Sipőcz, B. M., Brasseur, C. E., et al. 2019, AJ, 157, 98
  * Hunter (2007) Hunter, J. D. 2007, Computing in Science & Engineering, 9, 90
  * Im et al. (2023) Im, M., Paek, G. S. H., Jeong, M., et al. 2023, GRB Coordinates Network, 33449, 1
  * Levan et al. (2023) Levan, A. J., Gompertz, B., Ackley, K., Kennedy, M., & Dhillon, V. 2023, GRB Coordinates Network, 33439, 1
  * Li et al. (2012) Li, L., Liang, E.-W., Tang, Q.-W., et al. 2012, ApJ, 758, 27
  * O’Connor et al. (2023) O’Connor, B., Dichiara, S., Troja, E., et al. 2023, GRB Coordinates Network, 33447, 1
  * Oliphant (2007) Oliphant, T. E. 2007, Computing in Science & Engineering, 9, 10
  * Ricker et al. (2015) Ricker, G. R., Winn, J. N., Vanderspek, R., et al. 2015, Journal of Astronomical Telescopes, Instruments, and Systems, 1, 014003
  * Schlafly & Finkbeiner (2011) Schlafly, E. F., & Finkbeiner, D. P. 2011, ApJ, 737, 103
  * van der Walt et al. (2011) van der Walt, S., Colbert, S. C., & Varoquaux, G. 2011, Computing in Science & Engineering, 13, 22
  * Vanderspek et al. (2018) Vanderspek, R., Doty, J., Fausnaugh, M., et al. 2018, TESS Instrument Handbook, Tech. rep., Kavli Institute for Astrophysics and Space Science, Massachusetts Institute of Technology