In contrast, for finite algebras \(\mathbf {A}\)  in many
familiar classes, the subpower membership problem is in \(\mathsf {P}\) ,
that is, there is a polynomial time algorithm for solving the problem.
For example, if \(\mathbf {A}\)  is a group, then a variant of Sims' algorithm
(cf. [1]})
solves the problem in polynomial time.
Other simple algorithms work if
\(\mathbf {A}\)  is a finite lattice or a finite lattice with additional operations
(use the Baker–Pixley Theorem [2]})
or if \(\mathbf {A}\)  is a finite semilattice.
A recent result of A. Bulatov, M. Kozik, P. Mayr, and M. Steindl [3]}
extends this observation on semilattices
to any finite commutative semigroup \(\mathbf {A}\)  by
showing that if \(\mathbf {A}\)  embeds into a direct product of a Clifford semigroup
and a nilpotent semigroup, then the subpower membership problem for \(\mathbf {A}\) 
is in \(\mathsf {P}\) , and for all other finite commutative semigroups \(\mathbf {A}\) 
the problem is \(\mathsf {NP}\) -complete.
