Deciding some Maltsev conditions in finite idempotent algebras

Abstract

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 Jónsson (or Gumm) terms of fixed length.

33 pages, 19 figures

Cited by in corpus (5)

• Day's Theorem is sharp for $n$ even
• A short way to directed Jónsson terms
• Varieties defined by linear equations have the amalgamation property
• Between an $n$-ary and an $n+1$-ary near-unanimity term
• Deciding the existence of quasi weak near unanimity terms in finite algebras