On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909595937538048 |
|---|---|
| author | Grochow, Joshua A. Johnson, Dan Levet, Michael |
| author_facet | Grochow, Joshua A. Johnson, Dan Levet, Michael |
| contents | In this paper, we exhibit an $\textsf{AC}^{3}$ isomorphism test for groups without Abelian normal subgroups (a.k.a. Fitting-free groups), a class for which isomorphism testing was previously known to be in $\mathsf{P}$ (Babai, Codenotti, and Qiao; ICALP '12). Here, we leverage the fact that $G/\text{PKer}(G)$ can be viewed as permutation group of degree $O(\log |G|)$. As $G$ is given by its multiplication table, we are able to implement the solution for the corresponding instance of Twisted Code Equivalence in $\textsf{AC}^{3}$.
In sharp contrast, we show that when our groups are specified by a generating set of permutations, isomorphism testing of Fitting-free groups is at least as hard as Graph Isomorphism and Linear Code Equivalence (the latter being $\textsf{GI}$-hard and having no known subexponential-time algorithm).
Lastly, we show that any Fitting-free group of order $n$ is identified by $\textsf{FO}$ formulas (without counting) using only $O(\log \log n)$ variables. This is in contrast to the fact that there are infinite families of Abelian groups that are not identified by $\textsf{FO}$ formulas with $o(\log n)$ variables (Grochow & Levet, FCT '23). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_19777 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness Grochow, Joshua A. Johnson, Dan Levet, Michael Computational Complexity Data Structures and Algorithms Logic in Computer Science Group Theory 20A15, 68Q19, 68Q25 F.2.2; G.2.2; F.1.3; F.2.2 In this paper, we exhibit an $\textsf{AC}^{3}$ isomorphism test for groups without Abelian normal subgroups (a.k.a. Fitting-free groups), a class for which isomorphism testing was previously known to be in $\mathsf{P}$ (Babai, Codenotti, and Qiao; ICALP '12). Here, we leverage the fact that $G/\text{PKer}(G)$ can be viewed as permutation group of degree $O(\log |G|)$. As $G$ is given by its multiplication table, we are able to implement the solution for the corresponding instance of Twisted Code Equivalence in $\textsf{AC}^{3}$. In sharp contrast, we show that when our groups are specified by a generating set of permutations, isomorphism testing of Fitting-free groups is at least as hard as Graph Isomorphism and Linear Code Equivalence (the latter being $\textsf{GI}$-hard and having no known subexponential-time algorithm). Lastly, we show that any Fitting-free group of order $n$ is identified by $\textsf{FO}$ formulas (without counting) using only $O(\log \log n)$ variables. This is in contrast to the fact that there are infinite families of Abelian groups that are not identified by $\textsf{FO}$ formulas with $o(\log n)$ variables (Grochow & Levet, FCT '23). |
| title | On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness |
| topic | Computational Complexity Data Structures and Algorithms Logic in Computer Science Group Theory 20A15, 68Q19, 68Q25 F.2.2; G.2.2; F.1.3; F.2.2 |
| url | https://arxiv.org/abs/2504.19777 |