标题： 关于识别没有交换正规子群的群的复杂性：并行、一阶、以及GI-硬度 显示英文标题

标题： On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness

摘要： 本文中，我们展示了一种针对不含 Abel 正规子群（即拟 Fitting-自由群）的群的 $\textsf{AC}^{3}$ 同构测试方法，此前已知这类同构测试问题属于 $\mathsf{P}$ （Babai、Codenotti 和 Qiao；ICALP '12）。在这里，我们利用了 $G/\text{PKer}(G)$ 可被视为度数为 $O(\log |G|)$ 的置换群这一事实。由于 $G$ 由其乘法表给出，我们能够实现对应于 Twisted Code 等价问题的解决方案 $\textsf{AC}^{3}$。与此形成鲜明对比的是，我们证明当这些群由生成置换集指定时，拟 Fitting-自由群的同构测试至少与图同构和线性码等价一样困难（后者为 $\textsf{GI}$-难，且没有已知的次指数时间算法）。 最后，我们证明了任意阶为 $n$ 的Fitting-自由群都可以通过仅使用 $O(\log \log n)$ 个变量的 $\textsf{FO}$ 公式（不计数）来识别。 这与如下事实形成对比：存在无穷多个阿贝尔群族，它们无法通过 $o(\log n)$ 个变量的 $\textsf{FO}$ 公式来识别（Grochow & Levet, FCT '23）。 显示英文摘要

摘要： 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).