The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.

DOI10.1007/s00012-011-0163-yzbMath1236.16046OpenAlexW2002247104MaRDI QIDQ652516

Gábor Horváth

Publication date: 14 December 2011

Published in: Algebra Universalis (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2437/118923

zbMATH Keywords

computational complexityfinite ringsfinite nilpotent groupsequivalence problemequation solvability problemsring terms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Finite rings and finite-dimensional associative algebras (16P10) Nil and nilpotent radicals, sets, ideals, associative rings (16N40) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Finite nilpotent groups, (p)-groups (20D15) Operations and polynomials in algebraic structures, primal algebras (08A40) Computational aspects of associative rings (general theory) (16Z05) Algebraic geometry over groups; equations over groups (20F70)

Related Items (14)

Loosely-abelian algebras ⋮ Satisfiability in MultiValued Circuits ⋮ The complexity of the equation solvability problem over nilpotent groups ⋮ A survey on varieties generated by small semigroups and a companion website ⋮ Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\). ⋮ 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. ⋮ Unnamed Item ⋮ The equation solvability problem over supernilpotent algebras with Mal’cev term ⋮ The complexity of the equation solvability and equivalence problems over finite groups ⋮ Even Faster Algorithms for CSAT Over supernilpotent Algebras. ⋮ Evaluation of polynomials over finite rings via additive combinatorics ⋮ The complexity of the equivalence and equation solvability problems over meta-abelian groups

Cites Work

• The complexity of equivalence for commutative rings
• Complexity of the identity checking problem for finite semigroups.
• The equivalence problem for finite rings
• Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
• Results on the equivalence problem for finite groups.
• The complexity of checking identities for finite matrix rings
• Complexity issues of checking identities in finite monoids
• THE EQUIVALENCE PROBLEM OVER FINITE RINGS
• THE COMPLEXITY OF THE EQUIVALENCE PROBLEM OVER FINITE RINGS
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• The complexity of the word-problem for finite matrix rings
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• The complexity of the equivalence problem for nonsolvable groups
• Varieties of groups
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.