COMPLEXITY OF SEMIGROUP IDENTITY CHECKING

DOI10.1142/S0218196704001840MaRDI QIDQ4824699zbMATH OpenFDO

Authors Andrzej Kisielewicz

Publication date 1 November 2004

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0218196704001840

zbMATH Keywords

co-NP-complete problemscommutative semigroupscomputational complexityfinite semigroupsidentity checkingsemigroup identities

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Commutative semigroups (20M14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Review text

The author exhibits a semigroup \(S\) with less than \(2^{16}\) elements such that the identity checking problem for \(S\) (that is, the problem of determining, given two semigroup words \(u\) and \(v\), whether or not the identity \(u=v\) holds in \(S\)) is co-NP-complete (Theorem~1). The proof uses a reduction from MONOTONE 3SAT. It is also shown that for every finite commutative semigroup the problem can be solved in polynomial time (Theorem~4). Reviewer's remark: Recently O. Klima and S. Seif have independently proved that the identity checking problem for the 6-element Brandt monoid is co-NP-complete.

Recommendations

• Complexity of the identity checking problem for finite semigroups.
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
• Checking quasi-identities in a finite semigroup may be computationally hard.
• Complexity of the word problem for commutative semigroups of fixed dimension
• Complexity issues of checking identities in finite monoids

Cites work

• ALGORITHMIC PROBLEMS IN VARIETIES
• Bases for equational theories of semi-groups
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• Examples of varieties of semigroups
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• The complexity of equivalence for commutative rings
• The equivalence problem for finite rings

Cited in

(16)

• Checking quasi-identities in a finite semigroup may be computationally hard.
• Equivalence and equation solvability problems for the alternating group A₄.
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• Complexity issues of checking identities in finite monoids
• Complexity of identity checking in transformation semigroups of rank 2.
• Identity checking problem for transformation monoids
• Identities of the Kauffman Monoid $$\mathcal {K}_4$$ and of the Jones Monoid $$\mathcal {J}_4$$
• Identities of the Kauffman monoid \(\mathcal{K}_3\)
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
• ON COMPLETING PARTIAL GROUPOIDS TO SEMIGROUPS
• 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
• Complexity of the word problem for commutative semigroups of fixed dimension
• Complexity of the identity checking problem for finite semigroups.
• Word problem of the Perkins semigroup via directed acyclic graphs.
• An assertion concerning functionally complete algebras and NP-completeness

This page was built for publication: COMPLEXITY OF SEMIGROUP IDENTITY CHECKING

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4824699)