DECIDING SOME MALTSEV CONDITIONS IN FINITE IDEMPOTENT ALGEBRAS Academic Article uri icon

  •  
  • Overview
  •  
  • Research
  •  
  • Identity
  •  
  • Additional Document Info
  •  
  • View All
  •  

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\'onsson (or Gumm) terms of fixed length.