  We investigate the intersection problem for finite semigroups, which asks for
a given set of regular languages, represented by recognizing morphisms to
finite semigroups, whether there exists a word contained in their intersection.
We introduce compressibility measures as a useful tool to classify the
intersection problem for certain classes of finite semigroups into circuit
complexity classes and Turing machine complexity classes. Using this framework,
we obtain a new and simple proof that for groups and commutative semigroups,
the problem is contained in NP. We uncover certain structural and
non-structural properties determining the complexity of the intersection
problem for varieties of semigroups containing only trivial submonoids. More
specifically, we prove NP-hardness for classes of semigroups having a property
called unbounded order and for the class of all nilpotent semigroups of bounded
order. On the contrary, we show that bounded order and commutativity imply
containment in the circuit complexity class qAC^k (for some k) and decidability
in quasi-polynomial time. We also establish connections to the monoid variant
of the problem.
