Complexity of the identity checking problem for finite semigroups.
co-NP-complete problemscomputational complexitydecidability in polynomial timefinite semigroupsidentity checking problemsemigroups of transformationssolvable groups
Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05) Semigroups of transformations, relations, partitions, etc. (20M20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
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.
- COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
- Complexity of identity checking in transformation semigroups of rank 2.
- Checking quasi-identities in a finite semigroup may be computationally hard.
- On the computational complexity of matrix semigroup problems
- The complexity of properties of transformation semigroups
- Identity checking problem for transformation monoids
- scientific article; zbMATH DE number 4068272
- Complexity issues of checking identities in finite monoids
- Improved lower bounds for the complexity of finite semigroups
- Decidability of semigroup identities in soluble groups
- A 2EXPTIME complete varietal membership problem
- ALGORITHMIC PROBLEMS IN VARIETIES
- Complexity issues of checking identities in finite monoids
- COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
- Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
- Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
- COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
- COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS
- scientific article; zbMATH DE number 3875506 (Why is no real title available?)
- scientific article; zbMATH DE number 4028925 (Why is no real title available?)
- scientific article; zbMATH DE number 3574107 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
- On certain finitely based varieties of semigroups
- On Comparison of Finite Algebras
- Results on the equivalence problem for finite groups.
- SUBWORD COMPLEXITY OF PROFINITE WORDS AND SUBGROUPS OF FREE PROFINITE SEMIGROUPS
- The complexity of checking identities for finite matrix rings
- THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
- The complexity of equivalence for commutative rings
- The complexity of the equivalence problem for nonsolvable groups
- The complexity of the word-problem for finite matrix rings
- The equivalence problem for finite rings
- THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
- The intersection problem for finite semigroups
- Checking quasi-identities in a finite semigroup may be computationally hard.
- Equivalence and equation solvability problems for the alternating group A₄.
- Effective dimension of finite semigroups.
- Evaluation of polynomials over finite rings via additive combinatorics
- The complexity of the equivalence and equation solvability problems over meta-abelian groups
- Lower bounds on words separation: are there short identities in transformation semigroups?
- Complexity issues of checking identities in finite monoids
- Complexity of identity checking in transformation semigroups of rank 2.
- Identity checking problem for transformation monoids
- COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
- The complexity of properties of transformation semigroups
- Identities of the Kauffman Monoid $$\mathcal {K}_4$$ and of the Jones Monoid $$\mathcal {J}_4$$
- Words separation and positive identities in symmetric groups
- Identities of the Kauffman monoid \(\mathcal{K}_3\)
- THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
- INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
- ON COMPLETING PARTIAL GROUPOIDS TO SEMIGROUPS
- The intersection problem for finite semigroups
- On the complexity of inverse semigroup conjugacy
- Representations and identities of Baxter monoids with involution
- Representations and identities of hypoplactic monoids with involution
- Identities in twisted Brauer monoids
- The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
- Hardness of equations over finite solvable groups under the exponential time hypothesis
- Circuit equivalence in 2-nilpotent algebras
- On the complexity of properties of partial bijection semigroups
This page was built for publication: Complexity of the identity checking problem for finite semigroups.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q843593)
