The subpower membership problem for bands

Markus Steindl

paper

The subpower membership problem for bands

arXiv:1604.01014

Abstract

Fix a finite semigroup $S$ and let $a_{1}, \dots, a_{k}, b$ be tuples in a direct power $S^{n}$ . The subpower membership problem (SMP) for $S$ asks whether $b$ can be generated by $a_{1}, \dots, a_{k}$ . For bands (idempotent semigroups), we provide a dichotomy result: if a band $S$ belongs to a certain quasivariety, then $S M P (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.