The complexity of the equation solvability problem over semipattern groups

DOI10.1142/S0218196717500126MaRDI QIDQ2986663zbMATH OpenFDO

Authors Attila Földvári

Publication date 16 May 2017

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

Full work available at URL https://arxiv.org/abs/1603.05788

zbMATH Keywords

computational complexityequation solvabilityequivalencematrix ringsnilpotent ringspattern groupspolynomial time algorithmsemipattern groups

Mathematics Subject Classification ID

Nil and nilpotent radicals, sets, ideals, associative rings (16N40) Extensions, wreath products, and other compositions of groups (20E22) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Linear algebraic groups over finite fields (20G40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: The complexity of the equation solvability problem is known for nilpotent groups, for not solvable groups and for some semidirect products of Abelian groups. We provide a new polynomial time algorithm for deciding the equation solvability problem over certain semidirect products, where the first factor is not necessarily Abelian. Our main idea is to represent such groups as matrix groups, and reduce the original problem to equation solvability over the underlying field. Further, we apply this new method to give a much more efficient algorithm for equation solvability over nilpotent rings than previously existed.

Recommendations

• The complexity of the equation solvability and equivalence problems over finite groups
• The complexity of solving equations over finite groups
• The complexity of the equation solvability problem over nilpotent groups
• Dichotomies in the complexity of solving systems of equations over finite semigroups
• The complexity of solution sets to equations in hyperbolic groups
• Mathematical Foundations of Computer Science 2004
• The complexity of equivalence and isomorphism of systems of equations over finite groups
• Computing and Combinatorics
• The solubility of sets of equations over groups
• The complexity of the equivalence problem for nonsolvable groups

Cites work

• Counting characters of upper triangular groups.
• scientific article; zbMATH DE number 3392667 (Why is no real title available?)
• Results on the equivalence problem for finite groups.
• Supercharacters and superclasses for algebra groups
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• The complexity of equivalence for commutative rings
• The complexity of solving equations over finite groups
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• The complexity of the equivalence problem for nonsolvable groups
• The complexity of the equivalence problem over finite rings.
• The equivalence problem for finite rings
• THE EQUIVALENCE PROBLEM OVER FINITE RINGS

Cited in

(12)

• The complexity of the equation solvability problem over nilpotent groups
• Evaluation of polynomials over finite rings via additive combinatorics
• Solving a fixed number of equations over finite groups
• MPF problem over modified medial semigroup is NP-complete
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
• The equation solvability problem over supernilpotent algebras with Mal’cev term
• The complexity of the equation solvability and equivalence problems over finite groups
• Solving systems of equations in supernilpotent algebras
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• Hardness of equations over finite solvable groups under the exponential time hypothesis
• Dichotomies in the complexity of solving systems of equations over finite semigroups

This page was built for publication: The complexity of the equation solvability problem over semipattern groups

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