Mal'tsev condition satisfaction problems for conditions which imply edge terms
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.
scientific article; zbMATH DE number 7441049