Mal'tsev condition satisfaction problems for conditions which imply edge terms
type: Item
instance of: scholarly article
title: Mal'tsev condition satisfaction problems for conditions which imply edge terms
zbMATH Open document ID: 1485.08002
author: J. P. Rooney
published in: Algebra Universalis
publication date: 2021-12-08T00:00:00Z
review text: The paper considers the complexity of the problem of determining whether a finite idempotent algebra generates a variety which satisfies various Maltsev conditions. In particular, it is shown that if the strong Maltsev condition under consideration implies the existence of an edge term, then deciding whether a finite idempotent algebra generates a variety which satisfies the Maltsev condition is in the complexity class NP. In particular, the following theorems are proved. Theorem 4.1. Let \(k\) be a fixed integer greater than 1. There is a polynomial-time algorithm which takes as input a finite idempotent algebra \(A\) and returns a \(k\)-edge term operation of \(A\) whenever such a term exists. This algorithm is constructed by the author in the paper. Theorem 5.4 The decision problem for the uniform subpower membership problem with edge terms is in NP.
reviewed by: Ivan Chajda
Mathematics Subject Classification ID: 08A70
Mathematics Subject Classification ID: 08B05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7441049
zbMATH Keywords: Maltsev condition
zbMATH Keywords: satisfaction problem
zbMATH Keywords: edge terms
zbMATH Keywords: subpower membership problems
MaRDI profile type: Publication
full work available at URL: s00012-021-00754-1
OpenAlex ID: W3213944364
cites work: Congruence modularity implies cyclic terms for finite algebras
cites work: The wonderland of reflections
cites work: Varieties with few subalgebras of powers
cites work: Q4625700
cites work: Testing for a semilattice term
cites work: ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
cites work: The lattice of interpretability types of varieties
cites work: Computational complexity of various Mal'cev conditions
cites work: Deciding the Existence of Minority Terms
cites work: DECIDING SOME MALTSEV CONDITIONS IN FINITE IDEMPOTENT ALGEBRAS
cites work: Idempotent n -permutable varieties
DOI: 10.1007/S00012-021-00754-1
description: scientific article; zbMATH DE number 7441049