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].
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.