The complexity of the equation solvability and equivalence problems over finite groups

DOI10.1142/S0218196720500137MaRDI QIDQ4960464zbMATH OpenOpenAlexWikidataFDO

Authors Attila Földvári, Gábor Horváth

Publication date 16 April 2020

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

Full work available at URL https://doi.org/10.1142/s0218196720500137

zbMATH Keywords

computational complexityequation solvabilityequivalencepolynomial time algorithmsemidirect product of groups

Mathematics Subject Classification ID

Finite nilpotent groups, (p)-groups (20D15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Algebraic geometry over groups; equations over groups (20F70) Finite abelian groups (20K01) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of the equation solvability problem over semipattern groups
• The complexity of the equation solvability problem over nilpotent 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 extended equivalence and equation solvability problems for groups

Cites work

• A Contribution to the Theory of Groups of Prime-Power Order
• Equivalence and equation solvability problems for the alternating group A₄.
• scientific article; zbMATH DE number 3460471 (Why is no real title available?)
• scientific article; zbMATH DE number 534859 (Why is no real title available?)
• Results on the equivalence problem for finite groups.
• Symbolic Collection using Deep Thought
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• The complexity of solving 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
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• The complexity of the equivalence problem for nonsolvable groups

Cited in

(24)

• The complexity of the equation solvability problem over nilpotent groups
• The complexity of solving equations over finite groups
• Equivalence and equation solvability problems for the alternating group A₄.
• Cost of equivalence relations and groups
• Solving a fixed number of equations over finite groups
• Notes on extended equation solvability and identity checking for groups
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• The complexity of equivalence and isomorphism of systems of equations over finite groups
• Results on the equivalence problem for finite groups.
• The complexity of the equation solvability problem over semipattern groups
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• Detecting fast solvability of equations via small powerful Galois groups
• Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
• Even Faster Algorithms for CSAT Over supernilpotent Algebras.
• The complexity of the equivalence problem for nonsolvable groups
• The extended equivalence and equation solvability problems for groups
• A survey on varieties generated by small semigroups and a companion website
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• Constrained inhomogeneous spherical equations: average-case hardness
• Equation satisfiability in solvable groups
• Complexity of modular circuits
• Hardness of equations over finite solvable groups under the exponential time hypothesis
• Circuit equivalence in 2-nilpotent algebras
• Dichotomies in the complexity of solving systems of equations over finite semigroups

Describes a project that uses

Uses Software

• GAP
• SONATA

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

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