The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term

We consider finite algebraic structures and ask whether every solution of a given system of equations satisfies some other equation. This can be formulated as checking the validity of certain first order formulae called \emph{quasi-identities}. Checking the validity of quasi-identities is closely linked to solving systems of equations. For systems of equations over finite algebras with finitely many fundamental operations, a complete $\mathrm{P}/\mathrm{NPC}$ dichotomy is known, while the situation appears to be more complicated for single equations. The complexity of checking the validity of a quasi-identity lies between the complexity of term equivalence (checking whether two terms induce the same function) and the complexity of solving systems of polynomial equations. We prove that for each finite algebra with a Mal'cev term and finitely many fundamental operations, checking the validity of quasi-identities is $\coNP$-complete if the algebra is not abelian, and in $\PP$ when the algebra is abelian.