COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
Andrzej Kisielewicz · International Journal of Algebra and Computation · 2004
We consider the [Formula: see text] problem, whose instance is a finite semigroup S and an identity I, and the question is whether I is satisfied in S. We show that the question concerning computational complexity of this problem is much harder, when restricted to commutative semigroups. We provide a relatively simple proof that in general the problem is co-NP-complete, and demonstrate, using some structure theory, that for a fixed commutative semigroup the problem can be solved in polynomial time. The complexity status of the general [Formula: see text] problem remains open.