Algorithms make testing maps between special finite groups faster
Algorithms for Finite Group Epimorphism Testing
Data Structures and AlgorithmsComputational Complexity
Summary
The problem studied is about checking if there is a special kind of map, called an epimorphism, from one finite group to another. Groups are sets with operations that follow certain rules, and an epimorphism is a map that covers every element of the second group. The authors show that for some well-understood types of groups, this test can be done quickly using algorithms that run in polynomial time. These group types include ones with certain normal subgroups and well-behaved complements, expanding on previous work that focused on testing if groups are exactly the same. This helps us better understand how hard these kinds of problems are for different types of groups.
finite groupgroup homomorphismepimorphismpolynomial timeCayley tableAbelian groupHall subgroupelementary Abelian groupgroup isomorphismcomputational complexity
Authors
Joshua A. Grochow, Pranjal Srivastava, Dhara Thakkar
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.