2022/12/21 by Collins, Nathaniel A., Levet, Michael · 1 citation
#20-08 #20A15 #68Q17 #68Q19 #68Q25 #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #F.4.1 #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR) #I.1.2 #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2212.11247
We investigate the power of counting in Group Isomorphism. We first leverage the count-free variant of the Weisfeiler--Leman Version I algorithm for groups (Brachter & Schweitzer, LICS 2020) in tandem with limited non-determinism and limited counting to improve the parallel complexity of isomorphism testing for several families of groups. These families include: - Direct products of non-Abelian simple groups. - Coprime extensions, where the normal Hall subgroup is Abelian and the complement is an O(1)-generated solvable group with solvability class poly log log n. This notably includes instances where the complement is an O(1)-generated nilpotent group. This problem was previously known to be in \textsfP (Qiao, Sarma, & Tang, STACS 2011), and the complexity was recently improved to \textsfL (Grochow & Levet, FCT 2023). - Graphical groups of class 2 and exponent p > 2 (Mekler, J. Symb. Log., 1981) arising from the CFI and twisted CFI graphs (Cai, Fürer, & Immerman, Combinatorica 1992) respectively. In particular, our work improves upon previous results of Brachter & Schweitzer (LICS 2020). We finally show that the q-ary count-free pebble game is unable to distinguish even Abelian groups. This extends the result of Grochow & Levet (ibid), who established the result in the case of q = 1. The general theme is that some counting appears necessary to place Group Isomorphism into \textsfP.