Tue, 14 Apr 2026, 1:25 pm MDT
We study the subpower intersection problem ($\mathrm{SIP}$) for a fixed finite semigroup $S$: given sets $A,B \subseteq S^n$, decide whether the subsemigroups generated by $A$ and $B$ have nonempty intersection. We will present the following complexity results for $\mathrm{SIP}$ over finite semigroups. For every finite semigroup $S$, $\mathrm{SIP}(S)$ is in $\mathrm{PSPACE}$. For finite bands, $\mathrm{SIP}(S)$ is in $\mathrm{P}$ if $S$ is normal and is $\mathrm{NP}$-complete otherwise. For full transformation semigroups $T_n$, $\mathrm{SIP}(T_2)$ is $\mathrm{NP}$-complete and $\mathrm{SIP}(T_n)$ is $\mathrm{PSPACE}$-complete for $n \ge 3$. For finite (completely) simple semigroups, $\mathrm{SIP}(S)$ is in $\mathrm{P}$, and moreover $\mathrm{SIP}(S^1)$ is in $\mathrm{P}$ if $S$ is a group and is $\mathrm{NP}$-complete otherwise.
[video]