The complexity of the equivalence and equation solvability problems over meta-abelian groups

DOI10.1016/j.jalgebra.2015.03.015zbMath1364.20016OpenAlexW2127525529MaRDI QIDQ2343499

Gábor Horváth

Publication date: 6 May 2015

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

Full work available at URL: https://doi.org/10.1016/j.jalgebra.2015.03.015

zbMATH Keywords

computational complexitypolynomial-time algorithmsequations over groupsfinite metabelian groupsequation solvabilitymodule equivalence

Mathematics Subject Classification ID

Extensions, wreath products, and other compositions of groups (20E22) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Polynomials and finite commutative rings (13M10) Algebraic geometry over groups; equations over groups (20F70)

Related Items (12)

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 ⋮ Zero testing and equation solving for sparse polynomials on rectangular domains ⋮ 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. ⋮ 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 ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

Uses Software

• GAP
• SONATA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Identity checking problem for transformation monoids
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• The complexity of equivalence for commutative rings
• Complexity of the identity checking problem for finite semigroups.
• Word problem of the Perkins semigroup via directed acyclic graphs.
• Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\).
• 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.
• Complexity issues of checking identities in finite monoids
• THE EQUIVALENCE PROBLEM OVER FINITE RINGS
• TERM EQUATION SATISFIABILITY OVER FINITE ALGEBRAS
• THE COMPLEXITY OF THE EQUIVALENCE PROBLEM OVER FINITE RINGS
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• The complexity of the equivalence problem for nonsolvable groups

This page was built for publication: The complexity of the equivalence and equation solvability problems over meta-abelian groups