ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM
Markus Steindl · Journal of the Australian Mathematical Society · 2018
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) for $S$ asks whether $b$ can be generated by $a_{1},\ldots ,a_{k}$ . For combinatorial Rees matrix semigroups we establish a dichotomy result: if the corresponding matrix is of a certain form, then theSMPis in P; otherwise it is NP-complete. For combinatorial Rees matrix semigroups with adjoined identity, we obtain a trichotomy: theSMPis either in P, NP-complete, or PSPACE-complete. This result yields various semigroups with PSPACE-completeSMPincluding the six-element Brandt monoid, the full transformation semigroup on three or more letters, and semigroups of all $n$ by $n$ matrices over a field for $n\geq 2$ .