Hardness Results for the Subpower Membership Problem

2017/07/25 by Shriner, Jeff
#08B05 #68Q17 #FOS: Mathematics #Rings and Algebras (math.RA)

paper · doi:10.48550/arxiv.1707.08244

Abstract

The main result of this paper shows that if M is a consistent strong linear Maltsev condition which does not imply the existence of a cube term, then for any finite algebra \mathbbA there exists a new finite algebra \mathbbA_M which satisfies the Maltsev condition M, and whose subpower membership problem is at least as hard as the subpower membership problem for \mathbbA. We characterize consistent strong linear Maltsev conditions which do not imply the existence of a cube term, and show that there are finite algebras in varieties that are congruence distributive and congruence k-permutable (k ≥ 3) whose subpower membership problem is EXPTIME-complete.

Related

• Algebras from Congruences
• The subpower membership problem of 2-nilpotent algebras
• Existence of cube terms in finite algebras
• The class of congruence meet semidistributive varieties is not strong Maltsev
• Flexible constraint satisfiability and a problem in semigroup theory