THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS

DOI10.1142/S0218196706003256zbMATH Open1104.68051OpenAlexW2109957355MaRDI QIDQ3421602FDOQ3421602

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

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

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)

Cites Work

• Title not available (Why is that?)
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• The equivalence problem for finite rings
• Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
• The complexity of equivalence for commutative 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\).
• Complexity of modular circuits
• Solving a fixed number of equations over finite groups
• The complexity of the equation solvability problem over nilpotent groups
• 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)