On p -Group Isomorphism: Search-to-Decision, Counting-to-Decision, and Nilpotency Class Reductions via Tensors
Open Access
- 12 March 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 16 (1) , 1-39
Abstract
In this article, we study some classical complexity-theoretic questions regarding Group Isomorphism ( GpI ). We focus on p -groups (groups of prime power order) with odd p , which are believed to be a bottleneckcase for GpI , and work in the model of matrix groups over finite fields. Our main results are as follows: • Although search-to-decision and counting-to-decision reductions have been known for more than four decades for Graph Isomorphism , they had remained open for GpI , explicitly asked by Arvind and Torán ( EATCS Bull. , 2005). Extending methods from Tensor Isomorphism (TI) (Grochow and Qiao, ITCS 2021), we show moderately exponential-time such reductions within p -groups of class 2 and exponent p . • Despite the widely held belief that p -groups of class 2 and exponent p are the hardest cases of GpI , there was no reduction to these groups from any larger class of groups. Again using methods from TI (ibid.), we show the first such reduction, namely from isomorphismtesting of p -groups of “small” class and exponent p to those of class two and exponent p . For the first results, our main innovation is to develop linear-algebraic analogues of classical graph coloring gadgets, a key technique in studying the structural complexity of Graph Isomorphism . Unlike the graph coloring gadgets, which support restricting to various subgroups of the symmetric group, the problems we study require restricting to various subgroups of the general linear group, which entails significantly different and more complicated gadgets. The analysis of one of our gadgets relies on a classical result from group theory regarding random generation of classical groups (Kantor and Lubotzky, Geom. Dedicata , 1990). For the nilpotency class reduction, we combine a runtime analysis of the Lazard correspondence with TI-completeness results (Grochow and Qiao, ibid.).Keywords
Funding Information
- NSF (DMS-1750319)
- Australian Research Council (DP200100950)
This publication has 57 references indexed in Scilit:
- An effective version of the Lazard correspondenceJournal of Algebra, 2012
- Isomorphism in expanding families of indistinguishable groupsGroups - Complexity - Cryptology, 2012
- Settling the complexity of computing two-player Nash equilibriaJournal of the ACM, 2009
- Testing isomorphism of modulesJournal of Algebra, 2008
- Automorphism group computation and isomorphism testing in finite groupsJournal of Symbolic Computation, 2003
- CONSTRUCTING AUTOMORPHISM GROUPS OF p-GROUPSCommunications in Algebra, 2002
- Is code equivalence easy to decide?IEEE Transactions on Information Theory, 1997
- Computing the structure of finite algebrasJournal of Symbolic Computation, 1990
- Stability of nilpotent groups of class 2 and prime exponentThe Journal of Symbolic Logic, 1981
- A note on the graph isomorphism counting problemInformation Processing Letters, 1979