THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS

DOI10.1142/S0218196706003256MaRDI QIDQ3421602zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• The complexity of solving equations over finite groups
• Solving a fixed number of equations over finite groups
• The complexity of the equation solvability and equivalence problems over finite groups
• The extended equivalence and equation solvability problems for groups

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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
• The complexity of equivalence for commutative rings
• The equivalence problem for finite rings

Cited in

(19)

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

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

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