arXiv preprint ·
Algorithms for Finite Group Epimorphism Testing
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The Group Epimorphism Problem (GpEpi) asks, given two finite groups $G_1$ and $G_2$, whether there exists a surjective group homomorphism, or epimorphism, from $G_1$ to $G_2$. When the input groups are given by their multiplication (Cayley) tables, the problem admits a quasipolynomial-time algorithm in general, but little is known about its complexity for structured classes of finite groups. In this paper, we study the computational complexity of GpEpi for several well-studied classes of finite groups. Our main results are polynomial-time epimorphism tests for several classes of groups for which polynomial-time isomorphism testing was previously known: Groups with Abelian normal Hall subgroups with cyclic complement; Groups with (product of) elementary Abelian normal Hall subgroup with elementary Abelian complement; and Groups with some constraints on their Abelian chief factors.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
On the generation of multiplicative groups by small primes
Sample Complexity of Equivariant Reinforcement Learning
Quantum Algorithms for Minimum Generating Set
CAS II: Orbits as Models: Kolmogorov's Structure Function under Symmetry
Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.