Nonuniform Deterministic Finite Automata
over Finite Algebraic Structures

There are many interactions between mathematics and (theoretical) computer science. Many branches of these sciences influence each other, sometimes in quite surprising ways. A relatively recent example of such an influence is the so-called algebraic approach to Constraint Satisfaction Problem (CSP) which led to a complete classification of computational complexity of CSP [8, 36]. It is really impressive how in this case (universal) algebra, combinatorics, logic, computational complexity and algorithmic work together to give new results in each of these fields.

Another example of synergy between different fields of mathematics and theoretical computer science can be observed on the borderline of circuit complexity, automata theory and (universal) algebra. The most significant example here is the role of monoids played in automata theory and formal languages.

Usually a deterministic finite automaton (DFA) is determined by an alphabet $\mathrm{\Sigma }$ acting over a set $Q$ of states by a function $\delta :\mathrm{\Sigma }\times Q\ni (\sigma ,q)⟼\sigma \cdot q\in Q$. This action can be extended (in an obvious way) to the action of the free monoid ${\mathrm{\Sigma }}^{\ast }$. To decide if a word $w\in {\mathrm{\Sigma }}^{\ast }$ is accepted by a particular DFA we need to endow it with a starting state $q_0$ and a set $F\subseteq Q$ of accepting states. Then $w$ gets accepted if $w\cdot q_0\in F$. For our purposes we prefer, first to treat the set $Q^Q$ of functions as the monoid with $f\cdot g=g\circ f$, and then to treat the action $\delta$ as a function $a:\mathrm{\Sigma }⟶Q^Q$ given by $a(\sigma )(q)=\sigma \cdot q$. Now, the word ${\sigma }^1\mathrm{\dots }{\sigma }^n$ gets accepted if $a({\sigma }^1)\cdot \mathrm{\dots }\cdot a({\sigma }^n)\in S$, where $S$ consists of transitions determined by the words $w\in {\mathrm{\Sigma }}^n$ satisfying $w\cdot q_0\in F$.

Before restating Barrington’s definition of Non-uniform Deterministic Finite Automata (NUDFA) over monoids [3] we note that $a({\sigma }^1)\cdot \mathrm{\dots }\cdot a({\sigma }^n)$ is nothing else but ${𝐭}_n(a({\sigma }^1),\mathrm{\dots },a({\sigma }^n))$, where ${𝐭}_n(x_1,\mathrm{\dots },x_n)=x_1\cdot \mathrm{\dots }\cdot x_n$. In a NUDFA over the monoid $𝐌$ to accept the word from ${\mathrm{\Sigma }}^n$ we are going to relax the term $x_1\cdot \mathrm{\dots }\cdot x_n$ to an arbitrary semigroup term $𝐭(x_1,\mathrm{\dots },x_k)$ and replace one action $a:\mathrm{\Sigma }⟶Q^Q$ by a bunch of functions $a^x:\mathrm{\Sigma }⟶M$, one for each variable of $𝐭$. Now a $𝐭$-program (with inputs from ${\mathrm{\Sigma }}^n$ represented by an $n$-variable word $b_1\mathrm{\dots }{b}_n$) consists of:

• $\mathrm{■}$

  a set of $k$-instructions, one for each variable $x$ of $𝐭$, of the form $\iota (x)=(b^x,a^x)$, where $b^x$ is one of the variables $b_i$,

• $\mathrm{■}$

  and a set $S\subseteq M$ of accepting values.

Finally, a NUDFA over $𝐌$ is a sequence (possibly even nonrecursive) of programs
${({𝐭}_n,n,{\iota }_n,S_n)}_{n\in \mathbb{N}}$ with ${𝐭}_n(x_1,\mathrm{\dots },x_{k_n})$ being some terms of $𝐌$, $S_n\subseteq M$ and ${\iota }_n$ being the instructions for the variables of ${𝐭}_n$. A word $b_1\mathrm{\dots }{b}_n\in {\mathrm{\Sigma }}^n$ gets accepted by such a NUDFA if ${𝐭}_n(a^{x_1}(b^{x_1}),\mathrm{\dots },a^{x_{k_n}}(b^{x_{k_n}}))\in S_n$.

Originally Barrington considered mainly the Boolean case where $\mathrm{\Sigma }=\{0,1\}$ to study computational boundaries of non-uniform constant-memory computation. Such automata can be used to compute the Boolean functions of the form ${\{0,1\}}^n⟶\{0,1\}$. They also give an interesting algebraic insight into the internal structure of the class ${\text{NC}}^1$ [6]. Note that in the Boolean case $\mathrm{\Sigma }=\{0,1\}$ the function $a^x$ is given by the pair of values $a^x(0),a^x(1)$. In such a case, for simplicity we write $\iota (x)=(b^x,a^x(0),a^x(1))$.

A natural question that arises here is whether the language accepted by a particular NUDFA over $𝐌$ is nonempty. This problem reduces to:

• $\text{ProgSat}\left(𝐌\right)$:  Decide if a given program over $𝐌$ accepts at least one word.

The problem $\text{ProgSat}$ proved itself to be extremely useful in studying groups (and monoids) for which determining if an equation has a solution ($\text{PolSat}$) is in P. In fact the proof of Goldmann and Russell in [13] that each nilpotent group $𝐆$ has tractable $\text{PolSat}\left(𝐆\right)$ modifies a polynomial time algorithm for $\text{ProgSat}\left(𝐆\right)$. A study of connections between $\text{PolSat}$ and $\text{ProgSat}$ for finite monoids is given in [5]. Recently a complete classification of finite groups $𝐆$ with $\text{ProgSat}\left(𝐆\right)\in \text{RP}$, together with its consequences for $\text{PolSat}$ has been provided by Idziak, Kawałek and Krzaczkowski in [26].

Now the results of [26] allow us to complete the long term extensive investigations [9, 20, 17, 18, 11, 35, 25] on equivalence problem $\text{PolEqv}$ of polynomials (i.e. terms with some variables already evaluated) over finite groups.

The lower bound in our characterization relies on the randomized version of the Exponential Time Hypothesis (rETH), while the upper bounds explore the so-called Constant Degree Hypothesis (CDH). This hypothesis, introduced in [6], can be rephrased to state that for a fixed integer $d$, a prime $p$ and an integer $m$ which is not just a power of $p$, any 3-level circuit of the form ${\mathrm{𝖠𝖭𝖣}}_d\circ {\mathrm{𝖬𝖮𝖣}}_m\circ {\mathrm{𝖬𝖮𝖣}}_p$ requires exponential size to compute ${\mathrm{𝖠𝖭𝖣}}_n$ of arbitrary large arity $n$ (in which ${\mathrm{𝖠𝖭𝖣}}_d$ gates are in the input layer, ${\mathrm{𝖬𝖮𝖣}}_m$ gates are in the middle layer, and there is one ${\mathrm{𝖬𝖮𝖣}}_p$ gate in the output layer). The best known lower bound, due to Chattopadhyay et al. [10], for the size of ${\mathrm{𝖠𝖭𝖣}}_d\circ {\mathrm{𝖬𝖮𝖣}}_m\circ {\mathrm{𝖬𝖮𝖣}}_p$ computing ${\mathrm{𝖠𝖭𝖣}}_n$ is only superlinear. Much earlier CDH has been considered in many different contexts. Already in [6] the case $d=1$, i.e. no ${\mathrm{𝖠𝖭𝖣}}_d$ layer, has been confirmed. Also restrictions put either on the number of ${\mathrm{𝖠𝖭𝖣}}_d$ used locally, or on the local structure of ${\mathrm{𝖠𝖭𝖣}}_d\circ {\mathrm{𝖬𝖮𝖣}}_m$ fragments, allowed Grolmusz and Tardos [15, 14] to confirm CDH. Very recently Kawałek and Weiß [30] confirmed CDH for symmetric circuits.

In this paper, under these two complexity hypotheses (i.e. rETH and CDH), the characterization of finite groups with tractable $\text{ProgSat}$ from [26] is applied to obtain an unexpectedly different characterization for tractable $\text{PolEqv}$.

A surprising part of these investigations is that such characterization can not only be done, but that it can be stated, in terms of algebraic structure of the groups. In fact this reveals another connection between (universal) algebra and circuit complexity theory.

The goal of this paper is to leave the group realm and generalize ˜1.1 to a much broader setting of algebras. As we will see shortly this generalization is two-fold. First we generalize the concept of NUDFAs to cover automata working over arbitrary finite algebraic structure $𝐀$. This requires to define a program over $𝐀$ and can be done by simply replacing the monoid $𝐌$ by the algebra $𝐀$ and assume that this time $𝐭$ is a term of the algebra $𝐀$.

Second, in general algebraic context it is not clear which operations are to be chosen to be the basic ones. And this choice may be extremely important from computational point of view. Recall after [27], that adding the binary commutator operation $[x,y]=x^{-1}{y}^{-1}xy$ to the language of a group may exponentially shorten the size of the input. Indeed the term ${𝐭}_n(x_1,\mathrm{\dots },x_n)=[\mathrm{\dots }[[x_1,x_2],x_3]\mathrm{\dots },x_n]$ has linear size if the commutator operation is allowed, while after writing this term in the pure group language (of multiplication and the inverse) we see that the size $\left|{𝐭}_n\right|$ of ${𝐭}_n$ is $2\left|{𝐭}_{n-1}\right|+2$, as ${𝐭}_n(x_1,\mathrm{\dots },x_n)={𝐭}_{n-1}{(x_1,\mathrm{\dots },x_{n-1})}^{-1}\cdot x_n^{-1}\cdot {𝐭}_{n-1}(x_1,\mathrm{\dots },x_{n-1})\cdot x_n$, so that $\left|{𝐭}_n\right|$ is exponential in $n$. Actually for the alternating group ${𝐀}_4$ it is shown in [19] that $\text{PolSat}\left({𝐀}_4\right)$ is in P, while after endowing ${𝐀}_4$ with the commutator operation (and therefore shortening the size of inputs) the problem becomes NP-complete. A solution to this phenomenon has been proposed by Idziak and Krzaczkowski in [27] by presenting a term by the algebraic circuit that computes it. For example ${𝐭}_n(x_1,\mathrm{\dots },x_n)$ can be computed by the circuit of size $6n-5$ as shown by Figure 1.
Representing polynomials of an algebra with algebraic circuits leads to a modified version of $\text{ProgSat}$ which we explore in this paper.

• $\text{ProgCSat}\left(𝐀\right)$:  Decide if a given program $(𝐭,n,\iota ,S)$ over $𝐀$ accepts at least one word, where $𝐭$ is given by a circuit over $𝐀$.

Measuring the size of the input, i.e. the expression of the form $𝐩=𝐪$ by the lengths of the polynomials $𝐩$ and $𝐪$ or by the sizes of their algebraic circuits used to compute $𝐩$ and $𝐪$ give rise to either $\text{PolSat}$ or $\text{CSat}$ in the satisfiability setting or to $\text{PolEqv}$ or $\text{CEqv}$ in the equivalence setting. Note here that [27] argues that the complexity of $\text{CSat}\left(𝐀\right)$ and $\text{CEqv}\left(𝐀\right)$ is independent of which term operations of the algebra $𝐀$ are chosen to be the basic ones. This independence gives a hope for a characterization of algebras $𝐀$ with tractable $\text{CSat}\left(𝐀\right)$ or $\text{CEqv}\left(𝐀\right)$ in terms of algebraic structure of $𝐀$. Actually already a series of papers [21, 35, 23, 26, 27, 33] enforces a bunch of such necessary algebraic conditions for an algebra to have $\text{CSat}$ or $\text{CEqv}$ tractable. Not surprisingly solvability and nilpotency are among these conditions.

To define these two notions of solvability and nilpotency outside the group realm we need a notion of a commutator. However we need to work with a commutator $[\alpha ,\beta ]$ of two congruences $\alpha ,\beta$ (that in the group setting correspond to normal subgroups) instead of a commutator of elements of an algebra. For more details on the definition and the properties of commutator, we refer to the book [12] and Section 2. Here we only note that this concepts of commutator of congruences works smoothly only in some restricted setting of the so-called congruence modular varieties, i.e. equationally definable classes of algebras with modular congruence lattices. Fortunately this setting includes groups, rings, quasigroups, loops, Boolean algebras, Heyting algebras, lattices and almost all algebras related to logic. In groups, rings or Boolean/Heyting algebras the congruences are determined by normal subgroups, ideals or filters respectively. Obviously this new concept of commutator of normal subgroups coincides with the old one. The commutator of two ideals $I,J$ of a commutative ring is simply their algebraic product $I\cdot J$, while the commutator of filters in a Boolean/Heyting algebra is their intersection. Now we can say that a congruence $\alpha$ is abelian, nilpotent or solvable if $[\alpha ,\alpha ]=0_{𝐀}$, $[\mathrm{\dots }[[\alpha ,\alpha ],\alpha ],\mathrm{\dots }\alpha ]=0_{𝐀}$ or $[[[\alpha ,\alpha ],[\alpha ,\alpha ]],\mathrm{\dots }[[\alpha ,\alpha ],[\alpha ,\alpha ]]]=0_{𝐀}$ respectively (for some number of nested commutators). Here, $0_{𝐀}$ is the identity relation/congruence of $𝐀$. The algebra $𝐀$ itself is said to be abelian, nilpotent or solvable if the total congruence $1_{𝐀}$ collapsing everything is abelian, nilpotent or solvable, respectively.

Note that, for nilpotent groups, Boolean programs (of NUDFAs) compute $\mathrm{𝖠𝖭𝖣}$ functions only of bounded arity, i.e. for each nilpotent group $𝐆$ there is a constant $k$ such that ${\mathrm{𝖠𝖭𝖣}}_k$ is computable by no program over $𝐆$ [6]. This nonexpressibility phenomenon does not transfer to nilpotent algebras in general congruence modular context. The most natural example here is the algebra $({\mathbb{Z}}_6;+,\%2)$, i.e. the group $({\mathbb{Z}}_6;+)$ endowed with the unary operation $\%2$ computing the parity. In this algebra all the circuits of the form ${\mathrm{𝖬𝖮𝖣}}_2\circ {\mathrm{𝖬𝖮𝖣}}_3$ can be modeled so that ${\mathrm{𝖠𝖭𝖣}}_n$ can be expressed for all $n$ (however by exponential size of the circuits). This action of the prime $2$ acting over prime $3$ cannot occur in nilpotent groups. Indeed, due to the Sylow theorem, each finite nilpotent group is a product of $p$-groups. This decomposition prevents interaction between different primes, as they occur on different stalks/coordinates. And the lack of such interactions is crucial in bounding the arity of expressible ${\mathrm{𝖠𝖭𝖣}}_n$’s. Also in our considerations the finite nilpotent algebras that decompose into a product of algebras of prime power order occur naturally. They are known as supernilpotent algebras [7, 1]. We will return to this concept of supernilpotent algebras and its relativization to supernilpotent congruences in Section 2.

Now we are ready to state the other two main results of the paper.

Results from [26] that we use in the proof of ˜1.1 heavily rely on a method of representing terms/polynomials of finite solvable group $𝐆$ by bounded-depth circuits that use only modular gates. Besides the obvious requirement that the circuit representing a group-polynomial $𝐩$ has to compute the very same function as $𝐩$ does, we also want to control the size of the circuit to be polynomial in terms of the size (length) of $𝐩$.

A very similar approach can be found in [32], where M.​ Kompatscher considers generalizations of finite nilpotent groups, i.e.​ nilpotent algebras from the congruence modular varieties. He provides a method to rewrite circuits over such algebras to constant-depth circuits which, again, use only modulo-counting gates. These modular circuits, which appear in both of the mentioned cases, are known as CC-circuits. However, since [32] does not use the notion of a program/NUDFA, the author formulates his results for circuits over $𝐀$ representing only some specific functions. For those functions, it is natural how to interpret Boolean values $0/1$ in the non-Boolean algebra $𝐀$. In our paper, the notion of a program/NUDFA provides us with a formal framework which helps to relate the expressive power of algebraic structures to some standard circuit complexity classes. Here, we present a very precise characterization of functions computable by programs over algebras corresponding to polynomial-time cases of $\text{ProgCSat}$.

This theorem not only is an interesting result on its own, but also is crucial in proving ˜1.2 and 1.3. Quite a technical proof of ˜1.4 can be found in the full version of the paper on arXiv [24]. It combines advanced tools of commutator theory [12], as well as many combinatorial lemmas on how to compose / compress circuits using gates ${\mathrm{𝖬𝖮𝖣}}_m$. This is in line (and in some parts extends) with some of the earlier works on these circuits (see for instance [14, 15, 22]).

An algebra is a set called a universe together with a finite set of operations acting on it called basic operations of the algebra. We usually use boldface letter to denote the algebra and the very same letter, but with a regular font, to denote its universe. $\mathrm{Pol}𝐀$ is the polynomial clone of $𝐀$, that is the set of all polynomial operations of $𝐀$. An algebra $𝐀$ is polynomially equivalent to an algebra $𝐁$ if it is isomorphic to an algebra which has the same set of polynomial operations as $𝐁$. An induced algebra ${𝐀|}_S$ is a set $S$ with all polynomial operations of $𝐀$ closed on $S$ (or in other word polynomial operations that produce values in $S$ when applied to arguments from $S$). An idempotent function is a function $f$ such that $f(f(x))=f(x)$.

In proofs of intractability of $\text{ProgCSat}$ and $\text{CEqv}$ for algebras from congruence modular varieties the crucial role is played by Tame Congruence Theory (see [16] for details). This is a deep algebraic tool describing local behavior of finite algebras. TCT shows that locally finite algebras behave in one of following five ways:

1. 1.

   a finite set with a group action on it,

2. 2.

   a finite vector space over a finite field,

3. 3.

   a two-element Boolean algebra,

4. 4.

   a two-element lattice,

5. 5.

   a two-element semilattice.

By $\mathrm{typ}\left\{𝐀\right\}$, let us denote a subset of $\{\mathrm{𝟏},..,\mathrm{𝟓}\}$ which describes the local behaviours we can find in an algebra $𝐀$. Note that in a case of algebra $𝐀$ from a congruence modular variety only three types can appear in $\mathrm{typ}\left\{𝐀\right\}$, that is types 2, 3 and 4. In case of types 3 and 4 there has to be a two-element set $U$ (whose elements we call $0$ and $1$) such that

• $\mathrm{■}$

  there is a polynomial $𝐞$ of $𝐀$ fulfilling $𝐞(A)=U$,

• $\mathrm{■}$

  there are polynomials of $𝐀$ which behaves on $U$ like $\wedge$ and $\vee$,

• $\mathrm{■}$

  in case of type 3 there is also unary polynomial of $𝐀$ which is a negation on $U$.

If we can find type 3 or 4 in $\mathrm{typ}\left\{𝐀\right\}$, the complexity of both $\text{ProgCSat}$ and $\text{CEqv}$ is relatively easy to determine, as we shall see in forthcoming chapters. For this reason the most of the volume of the paper is devoted to algebras with $\mathrm{typ}\left\{𝐀\right\}=\{\mathrm{𝟐}\}$. In the congruence modular variety those are precisely the solvable algebras [12, 16]. In fact, some of the earlier papers already dealt with algebras that are solvable but not nilpotent, so we will be mostly concerned with the notion of nilpotency and its properties.

Every solvable (so in particular - nilpotent) algebra in the congruence modular variety is Malcev, i.e.​ it possesses a polynomial operation $𝐝$ satisfying the following identity: $𝐝(y,x,x)=𝐝(x,x,y)=y$. A standard example of Malcev algebras are groups with a Malcev term of the form $x\cdot y^{-1}\cdot z$. Unlike for groups, nilpotent algebras do not necessarily decompose into a direct product of algebras of prime power order. However, the technique contained in this paper splits an algebra into slices on which such nice decomposition can be observed.

To define this slicing properly, we need to consider congruences. Recall that congruence $\sigma$ of an algebra $𝐀$ is an equivalence relation which is preserved by the operations of $𝐀$. Such relations are naturally associated with surjective homomorphisms from $𝐀$ to $𝐀/\sigma$ mapping $x$ to ${[x]}_{\sigma }$ (equivalence class of $x$ in $\sigma$), so congruences are essentially generalization of normal subgroups of a group. Similarly as normal subgroups, congruences of an algebra form a lattice. From now on, we write $\mathrm{𝖢𝗈𝗇}𝐀$ for the set of all congruences of $𝐀$. Every element of a finite lattice can be written as a meet (join) of meet-irreducible (join-irreducible) elements, i.e.​ elements which cannot be written as a meet (join) of any other two elements of the lattice. These special elements, generating $\mathrm{𝖢𝗈𝗇}𝐀$, will play a significant role in our analysis.

For $\alpha ,\beta \in \mathrm{𝖢𝗈𝗇}𝐀$, by $I[\alpha ,\beta ]$ we mean a set of congruences $\gamma$ such that $\alpha ⩽\gamma ⩽\beta$. In case when $I[\alpha ,\beta ]=\{\alpha ,\beta \}$, i.e.​ there are no congruences between $\alpha$ and $\beta$, we call $\beta$ a cover of $\alpha$, we call $\alpha$ a subcover of $\beta$, and we call $\alpha ,\beta$ a covering pair. To highlight such a situation we write $\alpha \prec \beta$ for short. Whenever $\alpha$ is meet-irreducible (join-irreducible) congruence, then there is a unique congruence ${\alpha }^{+}$ (${\alpha }^{-}$) such that $\alpha \prec {\alpha }^{+}$ (${\alpha }^{-}\prec \alpha$). For a nilpotent algebra $𝐀$ from a congruence modular variety whenever its congruences $\alpha ,\beta$ satisfy $\alpha \prec \beta$, the cosets (congruence classes) of $\beta /\alpha$ in $𝐀/\alpha$ have equal sizes, being a power of some prime (this is a consequence of the results contained in the fifth and seventh chapters of [12]). We later denote this prime by $\mathrm{𝖼𝗁𝖺𝗋}(\alpha ,\beta )$ and call it a characteristic of a congruence cover $\alpha \prec \beta$. Moreover for arbitrary , we write $\mathrm{𝖼𝗁𝖺𝗋}\{\alpha ,\beta \}$ for the set of all possible prime characteristics of covering pairs, which are fully contained in $I[\alpha ,\beta ]$. We say that a pair of congruences of a nilpotent algebra $𝐀$ forms a Prime Uniform Product Interval (PUPI), if there are congruences such that

• $\mathrm{■}$

  $\bigvee {\alpha }_i=\beta$

• $\mathrm{■}$

  ${\alpha }_i\wedge ({\bigvee }_{j\ne i}{\alpha }_j)=\alpha$, for $i,j\in \{1..k\}$,

• $\mathrm{■}$

  For every $i$ we have $|\mathrm{𝖼𝗁𝖺𝗋}\{\alpha ,{\alpha }_i\}|=1$.

We call a congruence $\beta$ supernilpotent whenever it is nilpotent and the interval $I[0_{𝐀},\beta ]$ is a PUPI, and we call an algebra $𝐀$ supernilpotent, whenever $1_{𝐀}$ is supernilpotent. Each supernilpotent algebra is isomorphic to a direct product of nilpotent algebras of prime power size. In this sense supernilpotence generalizes nilpotence for groups. Note that this definition is equivalent to a standard definition of supernilpotent algebras in congruence modular varieties [34].

We say that a nilpotent algebra $𝐀$ has supernilpotent rank $k$ whenever $k$ is the smallest number for which we can find sequence of congruences such that interval $I[{\alpha }_i,{\alpha }_{i+1}]$ is a PUPI for each . Note that for a finite nilpotent algebra $𝐀$ we can always find such a finite sequence, since each covering pair forms a PUPI. This notion of supernilpotent rank of an algebra, later denoted by $\mathrm{𝗌𝗋}\left(𝐀\right)$, proved to be extremely useful in some very recent results on the computation complexity of circuit satisfiability problem [21, 33]. In fact, results for $\text{ProgCSat}/\text{CEqv}$ we present in this paper, are essentially about nilpotent algebras with $\mathrm{𝗌𝗋}\left(A\right)=2$.

Our characterization of polynomial time cases of $\text{PolEqv}$ is achieved through a reduction to some special instances of $\text{PolSat}$. It was already noticed in [13] that $\text{PolSat}\left(𝐆\right)$ for finite group $𝐆$ reduces in polynomial time to $\text{ProgSat}\left(𝐆\right)$. Very recently, the full characterization of groups for which $\text{ProgSat}$ can be solved in randomized polynomial time was shown under the assumptions of rETH and CDH in [26].

˜3.1 together with a result from [25] provides us with enough information to prove the ˜1.1.

The goal of this section is to prove ˜1.2. First we observe in ˜4.1 that if a nilpotent algebra has a Malcev term then $\text{CSat}$ and $\text{CEqv}$ for this algebra reduce to $\text{ProgCSat}$. Thus, intractability of $\text{CSat}$ or $\text{CEqv}$ implies intractability of $\text{ProgCSat}$ and conversely if $\text{ProgCSat}$ is in RP, then $\text{CSat}$ is in RP and $\text{CEqv}$ is in coRP.

In this section we will prove ˜1.3. To do it we will show that solving $\text{CEqv}$ for an algebra $𝐀$ can be reduced to solving the very same problem for quotients of $𝐀$ by a meet-irreducible congruences. Obviously, every quotient algebra by a meet-irreducible congruence has the smallest congruence bigger than the identity relation. This observation plays a crucial role in the proof of ˜1.3.

The Constant Degree Hypothesis plays a crucial role in our proofs of the existence of randomized polynomial-time algorithms. One can ask if this assumption is really needed. In fact, there are some unconditional results. For example very recent paper [29] shows that $\text{CEqv}\left(𝐀\right)$ is in P whenever $𝐀$ from a congruence modular variety is $2$-nilpotent, i.e. it has abelian congruence with abelian quotient. Also supernilpotent algebras admit (unconditional) polynomial-time algorithm for $\text{CSat}$/$\text{CEqv}$ [1, 31, 27], and if we allow random bits the time complexity drops down to linear [28]. Unfortunately, it is not hard to construct for a given $d$, $m$, $p$ an algebra $𝐀$ with supernilpotent rank equal $2$ such that functions computable by ${\mathrm{𝖠𝖭𝖣}}_d\circ {\mathrm{𝖬𝖮𝖣}}_m\circ {\mathrm{𝖬𝖮𝖣}}_p$-circuit are exactly functions computable by, not too long, programs over $𝐀$. This, together with our results, shows that (under ETH) showing unconditional algorithms solving $\text{ProgCSat}$ for algebras from congruence modular variety with supernilpotent rank equal $2$ is equivalent to proving CDH. Hence, the natural question is if CDH holds.

The natural next step in our investigations is to go outside of the congruence modular realm. The first problem in such a case is that Tame Congruence Theory and Commutator Theory (our heavily used tools) for arbitrary algebras do not work as well as for algebras from congruence modular varieties. Moreover [27, Example 2.8] shows that there is an algebra $𝐀$ (not contained in congruence modular variety) and its congruence $\sigma$ such that $\text{CSat}\left(𝐀\right)$ is in P, while $\text{CSat}\left(𝐀/\sigma \right)$ is NP-complete. This suggests that we cannot expect a nice characterization of polynomial-time cases for $\text{CSat}$ outside congruence modular setting. On the other hand, we are not aware of any such examples for $\text{ProgCSat}$ and $\text{CEqv}$. In fact we saw that the hardness of $\text{ProgCSat}\left(𝐀/\sigma \right)$ implies the hardness for $\text{ProgCSat}\left(𝐀\right)$. This gives hope for characterization of tractable cases of $\text{ProgCSat}$ for general finite algebras.