The subpower membership problem for bands

2016/04/02 by Steindl, Markus
#20M99 #68Q25 #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.1604.01014

Abstract

Fix a finite semigroup S and let a₁,…,a_k, b be tuples in a direct power Sⁿ. The subpower membership problem (SMP) for S asks whether b can be generated by a₁,…,a_k. For bands (idempotent semigroups), we provide a dichotomy result: if a band S belongs to a certain quasivariety, then SMP(S) is in P; otherwise it is NP-complete. Furthermore we determine the greatest variety of bands all of whose finite members induce a tractable SMP. Finally we present the first example of two finite algebras that generate the same variety and have tractable and NP-complete SMPs, respectively.

Related

• The subpower membership problem for semigroups
• The subpower membership problem of 2-nilpotent algebras
• Flexible constraint satisfiability and a problem in semigroup theory
• Hardness Results for the Subpower Membership Problem
• Concrete algorithms for word problem and subsemigroup problem for\n semigroups which are disjoint unions of finitely many copies of the free\n monogenic semigroup