In this paper we investigate the computational complexity of deciding if a given finite algebraic structure satisfies a fixed (strong) Maltsev condition $Sigma$. Our goal in this paper is to show that $Sigma$-testing can be accomplished in polynomial time when the algebras tested are idempotent and the Maltsev condition $Sigma$ can be described using paths. Examples of such path conditions are having a Maltsev term, having a majority operation, and having a chain of Jonsson (or Gumm) terms of fixed length.
Download