Mal'tsev condition satisfaction problems for conditions which imply edge terms (Q2057105)

The paper considers the complexity of the problem of determining whether a finite idempotent algebra generates a variety which satisfies various Maltsev conditions. In particular, it is shown that if the strong Maltsev condition under consideration implies the existence of an edge term, then deciding whether a finite idempotent algebra generates a variety which satisfies the Maltsev condition is in the complexity class NP. In particular, the following theorems are proved. Theorem 4.1. Let \(k\) be a fixed integer greater than 1. There is a polynomial-time algorithm which takes as input a finite idempotent algebra \(A\) and returns a \(k\)-edge term operation of \(A\) whenever such a term exists. This algorithm is constructed by the author in the paper. Theorem 5.4 The decision problem for the uniform subpower membership problem with edge terms is in NP.