Computational Complexity of Finding Subgroups of a Given Order

2025/03/14 by Lakshmanan, K.
Biochemistry, Genetics and Molecular Biology · Mathematics · #20-08 #68Q17 #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #Genome Rearrangement Algorithms #Geometric and Algebraic Topology #Group Theory (math.GR)

paper · pdf · doi:10.48550/arxiv.2503.11238

openalex publication_date 2025/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the problem of finding a subgroup of a given order in a finite group, where the group is represented by its Cayley table. We analyze the complexity of the problem in the special case of abelian groups and present an optimal algorithm for finding a subgroup of a given order when the input is given in the form of a Cayley table. To the best of our knowledge, no prior work has addressed the complexity of this problem under the Cayley table representation.

Related

• The Parallel Dynamic Complexity of the Abelian Cayley Group Membership Problem
• Subgroups of minimal index in polynomial time
• Most Rigid Representations and Cayley index
• On the Complexity of the Cayley Semigroup Membership Problem
• Non-commutative lattice problems