Deciding some Maltsev conditions in finite idempotent algebras

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

No reviews yet.

No comments yet.