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

DOI10.1142/S0218196720500137zbMATH Open1484.20056OpenAlexW2988191270WikidataQ114614797 ScholiaQ114614797MaRDI QIDQ4960464FDOQ4960464

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

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

zbMATH Keywords

computational complexityequivalencepolynomial time algorithmsemidirect product of groupsequation solvability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Cites Work

• Title not available (Why is that?)
• The complexity of solving equations over finite groups
• Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\).
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• Title not available (Why is that?)
• Symbolic Collection using Deep Thought
• A Contribution to the Theory of Groups of Prime-Power Order
• Results on the equivalence problem for finite groups.
• The complexity of the equivalence problem for nonsolvable groups
• 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

Cited In (22)

• Notes on extended equation solvability and identity checking for groups
• Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
• The complexity of the equivalence problem for nonsolvable groups
• Constrained inhomogeneous spherical equations: average-case hardness
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• Detecting fast solvability of equations via small powerful Galois groups
• Equation satisfiability in solvable groups
• Dichotomies in the complexity of solving systems of equations over finite semigroups
• The complexity of equivalence and isomorphism of systems of equations over finite groups
• Even Faster Algorithms for CSAT Over supernilpotent Algebras.
• The extended equivalence and equation solvability problems for groups
• The complexity of solving equations over finite groups
• 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
• Results on the equivalence problem for finite groups.
• A survey on varieties generated by small semigroups and a companion website
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• Cost of equivalence relations and groups

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)