THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS

DOI10.1142/S0218196706003256zbMath1104.68051OpenAlexW2109957355MaRDI QIDQ3421602

Gábor Horváth, Csaba Szabó

Publication date: 7 February 2007

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

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

zbMATH Keywords

computational complexityfinite groupsterm equivalencefinite metabelian groupsidentity checkingequation solvability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (17)

Loosely-abelian algebras ⋮ Complexity of the identity checking problem for finite semigroups. ⋮ Complexity issues of checking identities in finite monoids ⋮ Satisfiability in MultiValued Circuits ⋮ The complexity of the equation solvability problem over nilpotent groups ⋮ Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\). ⋮ Identity checking problem for transformation monoids ⋮ The complexity of the equivalence and equation solvability problems over nilpotent rings and groups. ⋮ The complexity of the equation solvability problem over semipattern groups ⋮ Solving a fixed number of equations over finite groups ⋮ Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras. ⋮ An assertion concerning functionally complete algebras and NP-completeness ⋮ The equation solvability problem over supernilpotent algebras with Mal’cev term ⋮ TERM EQUATION SATISFIABILITY OVER FINITE ALGEBRAS ⋮ The complexity of the equation solvability and equivalence problems over finite groups ⋮ Even Faster Algorithms for CSAT Over supernilpotent Algebras. ⋮ The complexity of the equivalence and equation solvability problems over meta-abelian groups

Cites Work

• Unnamed Item
• The complexity of equivalence for commutative rings
• The equivalence problem for finite rings
• Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS

This page was built for publication: THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS