The subpower membership problem for semigroups

2016/03/29 by Bulatov, Andrei, Kozik, Marcin, Mayr, Peter +1
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.1603.09333

Abstract

Fix a finite semigroup S and let a₁,…,a_k, b be tuples in a direct power Sⁿ. The subpower membership problem (SMP) asks whether b can be generated by a₁,…,a_k. If S is a finite group, then there is a folklore algorithm that decides this problem in time polynomial in nk. For semigroups this problem always lies in PSPACE. We show that the SMP for a full transformation semigroup on 3 letters or more is actually PSPACE-complete, while on 2 letters it is in P. For commutative semigroups, we provide a dichotomy result: if a commutative semigroup S embeds into a direct product of a Clifford semigroup and a nilpotent semigroup, then SMP(S) is in P; otherwise it is NP-complete.

Related

• The subpower membership problem for bands
• Membership and Conjugacy in Inverse Semigroups
• The subpower membership problem of 2-nilpotent algebras
• 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
• On the Complexity of Properties of Partial Bijection Semigroups