Reduction of the group isomorphism problem to the group automorphism problem

2025/03/03 by Skresanov, Saveliy V. · 1 citation
#68Q25 (Primary) 20D45 (Secondary) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.2503.01180

Abstract

It is well known that the graph isomorphism problem is polynomial-time reducible to the graph automorphism problem (in fact these two problems are polynomial-time equivalent). We show that, analogously, the group isomorphism problem is polynomial-time reducible to the group automorphism problem. Reductions to other relevant problems like automorphism counting are also given.

Cited by

• Efficient Identification of Permutation Symmetries in Many-Body Hamiltonians via Graph Theory

Related

• The polynomial algorithm for graphs' isomorphism testing
• The Isomorphism Problem of Power Graphs and a Question of Cameron
• Graph isomorphism and automorphism problems are polynomial
• The direct algorithm for solving of the graph isomorphism problem
• Beating the Generator-Enumeration Bound for p-Group Isomorphism