Checking quasi-identities in a finite semigroup may be computationally hard. (Q1770618)

Many basic questions in algebra turn out to be (computationally) surprisingly difficult. For instance, it was shown by \textit{C. Bergman} and \textit{G. Slutzki} [SIAM J. Comput. 30, No. 2, 359-382 (2000; Zbl 0963.68077)] that the question of whether two finite algebras satisfy the same quasi-identities is NP-complete. This paper considers the question of whether a fixed finite algebra satisfies a given identity. This clearly belongs to co-NP, and in this paper a 10 element semigroup for which the question is co-NP complete is constructed. This is not the smallest possible such semigroup, but it is of interest because the checking of identities in it can be done in low polynomial time.