Checking quasi-identities in a finite semigroup may be computationally hard.
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.
scientific article; zbMATH DE number 2153450