We study the subpower intersection problem (SIP) for a fixed finite semigroup S: given sets A,B of n-tuples A,B over S, decide whether the subsemigroups generated by A and B have nonempty intersection. We will present the following complexity results for SIP over finite semigroups. For every finite semigroup S, SIP(S) is in PSPACE. For finite bands, SIP(S) is in P if S is normal and is NP-complete otherwise. For full transformation semigroups T_n, SIP(T_2) is NP-complete and SIP(T_n) is PSPACE-complete for n > 2. For finite (completely) simple semigroups, SIP(S) is in P, and moreover SIP(S^1) is in P if S is a group and is NP-complete otherwise.
The subpower intersection problem for finite semigroups
The subpower intersection problem for finite semigroups