Complexity of the identity checking problem for finite semigroups. (Q843593): Difference between revisions

Let \(S\) be a finite semigroup and \(G\) be the direct product of all its maximal subgroups. There exists a polynomial reduction of the identity checking problem in semigroup \(S\) to the identity checking problem in the group \(G\). This theorem and results from \textit{G. Horváth, J. Lawrence, L. Mérai} and \textit{Cs. Szabó}, [Bull. Lond. Math. Soc. 39, No. 3, 433-438 (2007; Zbl 1167.20019)], imply the following corollary. If a finite semigroup contains a nonsolvable subgroup, then identity checking in the semigroup is co-NP-complete. Combining this corollary with some known results one can obtain the following result. Identity checking in the semigroup of all \(n\times n\)-matrices over a finite field is co-NP-complete for \(n>1\) and is decidable in polynomial time for \(n=1\). The second theorem is the following. Identity checking in the semigroup of all transformations on an \(n\)-element set is co-NP-complete for \(n=3\) and \(n\geq 5\) and is decidable in polynomial time for \(n=1\), \(2\). The question about the complexity of identity checking in the semigroup of all transformations on a set with 4 elements still remains open.