The subpower membership problem for semigroups

DOI10.1142/S0218196716500612MaRDI QIDQ5298321zbMATH OpenFDO

Authors Andrei A. Bulatov, Marcin Kozik, Peter Mayr, Markus Steindl

Publication date 14 December 2016

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.09333

zbMATH Keywords

direct powermembership problemsemigroup

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) General structure theory for semigroups (20M10) Analysis of algorithms and problem complexity (68Q25)

Abstract: Fix a finite semigroup $S$ and let $a_1,ldots,a_k,b$ be tuples in a direct power $S^n$. The subpower membership problem (SMP) asks whether $b$ can be generated by $a_1,ldots,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.

Recommendations

• ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM
• Powers of subsets in a finite semigroup
• The subpower membership problem for Mal'cev algebras
• scientific article; zbMATH DE number 1972795
• The subpower membership problem for finite algebras with cube terms
• The subpower membership problem for bands
• On the structure of subordinate semigroups
• On subsemigroups of finitely presented semigroups
• scientific article; zbMATH DE number 3182220
• The Cayley semigroup membership problem

Cites work

• scientific article; zbMATH DE number 3722702 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 789816 (Why is no real title available?)
• Relationships between nondeterministic and deterministic tape complexities
• The subpower membership problem for Mal'cev algebras
• Tractability and learnability arising from algebras with few subpowers

Cited in

(13)

• The subpower membership problem for bands
• Powers of subsets in a finite semigroup
• Algebras from congruences
• scientific article; zbMATH DE number 4068272 (Why is no real title available?)
• The subpower membership problem for finite algebras with cube terms
• ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM
• Hardness results for the subpower membership problem
• The complexity of properties of transformation semigroups
• The Cayley semigroup membership problem
• scientific article; zbMATH DE number 7250165 (Why is no real title available?)
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• The subpower membership problem of 2-nilpotent algebras
• Symmetries and complexity (invited talk)

This page was built for publication: The subpower membership problem for semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5298321)