Complexity of the identity checking problem for finite semigroups.
type: Item
instance of: scholarly article
title: Complexity of the identity checking problem for finite semigroups.
zbMATH Open document ID: 1213.20052
author: S. V. Goldberg
author: Jorge Almeida
author: M. V. Volkov
published in: Journal of Mathematical Sciences (New York)
publication date: 2010-01-15T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 20M20
Mathematics Subject Classification ID: 20F10
zbMATH DE Number: 5659076
zbMATH Keywords: finite semigroups
zbMATH Keywords: computational complexity
zbMATH Keywords: identity checking problem
zbMATH Keywords: decidability in polynomial time
zbMATH Keywords: co-NP-complete problems
zbMATH Keywords: solvable groups
zbMATH Keywords: semigroups of transformations
MaRDI profile type: Publication
full work available at URL: s10958-009-9397-z
OpenAlex ID: W2044956773
cites work: SUBWORD COMPLEXITY OF PROFINITE WORDS AND SUBGROUPS OF FREE PROFINITE SEMIGROUPS
cites work: Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
cites work: The equivalence problem for finite rings
cites work: Results on the equivalence problem for finite groups.
cites work: On certain finitely based varieties of semigroups
cites work: Q4198056
cites work: The complexity of the equivalence problem for nonsolvable groups
cites work: THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
cites work: The complexity of equivalence for commutative rings
cites work: INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
cites work: On Comparison of Finite Algebras
cites work: Q3342725
cites work: ALGORITHMIC PROBLEMS IN VARIETIES
cites work: COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
cites work: Complexity issues of checking identities in finite monoids
cites work: COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS
cites work: A 2EXPTIME Complete Varietal Membership Problem
cites work: Q4145882
cites work: Q4298260
cites work: Q3769981
cites work: THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
cites work: Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
cites work: The complexity of the word-problem for finite matrix rings
cites work: The complexity of checking identities for finite matrix rings
cites work: COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
DOI: 10.1007/S10958-009-9397-Z
Recommended article: COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
Recommended article: Q3450090
Recommended article: Checking quasi-identities in a finite semigroup may be computationally hard.
Recommended article: On the computational complexity of matrix semigroup problems
Recommended article: The complexity of properties of transformation semigroups
Recommended article: Identity checking problem for transformation monoids
Recommended article: Q3801066
Recommended article: Complexity issues of checking identities in finite monoids
Recommended article: Improved lower bounds for the complexity of finite semigroups
Recommended article: Decidability of semigroup identities in soluble groups
description: scientific article; zbMATH DE number 5659076