Finite Semigroups and Computational Complexity

Many basic questions in algebra give rise to fascinating and sometimes very hard problems if one looks at these questions from the standpoint of feasible computations. In the talk, I will survey recent developments in studying computational complexity of two such natural questions in the equational theory of finite semigroups. Let us fix a finite semigroup S. Then CHECK-ID(S) is the decision problem whose input is an arbitrary semigroup identity and whose question is whether or not the identity holds in S. I will present a few results due to Klima, Lawrence, Pleshcheva, Seif, Szabo, Vertesi, Willard and myself that aim towards a classification of finite semigroups S for which CHECK-ID(S) is coNP-complete. Similarly, MEMB-VAR(S) is the decision problem whose input is an arbitrary finite semigroup and whose question is whether or not the semigroup belongs to the variety generated by S. I will present a series of examples (found by McKenzie and simplified by Jackson) of finite semigroups S for which MEMB-VAR(S) is NP-hard.