**Complexity of checking identities
and quasi-identities in finite semigroups**

M. V. Volkov

*Ural State University, Russia*

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. Several problems
of such kind related to varieties and quasivarieties generated
by finite algebras have been examined in the recent paper [1].
Questions which we deal with in the present talk are in a certain
sense even more fundamental than the questions considered in [1].
While there one basically asks whether a given finite algebra *A*
satisfies each of the (infinitely many) [quasi-]identities
holding in another given algebra *A'* and vice versa,
here
we concentrate on a single act of satisfaction by asking,
for any fixed finite algebra *A*, if it satisfies a given
[quasi-]identity.

We exhibit a 10-element 0-simple semigroup *Q* such that the problem
"*Does a given quasi-identity hold in **Q*?" is **co-NP**-complete.
We also describe several constructions of finite semigroups which behave
in a similar way with respect to checking identities. One of these
constructions (which yields a 240-element simple semigroup *R* such that
checking a given identity in *R* is **co-NP**-complete) is based
on John Rhodes's early result [2] on finite simple non-abelian
groups which is already known to have rather surprising connections
to other parts of complexity theory, see [3].

## References

- [1]
- C. Bergman and G. Slutzki,
*Complexity of some problems concerning
varieties and quasi-varieties of algebras*, SIAM J. Comput. **30**
(2000) 359-382.

- [2]
- W. D. Maurer and J. L. Rhodes,
*A property of finite simple non-abelian
groups*, Proc. Amer. Math. Soc. **16** (1965) 552-554.

- [3]
- H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity,
Birkhäuser, Boston, 1994.

Sponsored in part by the FCT approved
projects POCTI 32817/99 and POCTI/MAT/37670/2001 in participation with
the European Community Fund FEDER and by FCT through *Centro de Matemática
da Universidade do Porto.* Also sponsored in part by FCT, the
*Faculdade de Ciências da Universidade do Porto, Programa Operacional Ciência, Tecnologia, Inovação do Quadro Comunitário de Apoio III*, and by *Caixa Geral de Depósitos*.

File translated from T_{E}X by T_{T}H, version 1.92.

On 4 Apr 2002, 18:01.