论文标题
无数的weisfeiler-勒曼和小组同构
Count-Free Weisfeiler--Leman and Group Isomorphism
论文作者
论文摘要
我们研究了组同构的计数能力。我们首先利用weisfeiler-leman版本I算法的无计数变体（Brachter＆Schweitzer，LICS 2020）列出，非确定性和有限的计数，以提高几个组家族的同构测试的平行复杂性。这些家庭包括： - 非亚洲简单群体的直接产品。 - 副扩展，其中正常的大厅子组为Abelian，补充是$ O（1）$ - 生成的可解决的群体，可解决性类别$ \ text {poly} \ log \ log \ log \ log n $。这值得注意的是，补充为$ O（1）$ - 生成的nilpotent组。以前已知此问题以$ \ textsf {p} $（qiao，sarma＆Tang，Stacs 2011）为单位，并且最近将复杂性提高到$ \ textsf {l} $（Grochow＆Levet，FCT 2023）。 - 分别由CFI和Twisted CFI图（CAI，Fürer，＆Immerman，Combinatorica 1992）引起的类别的$ 2 $和指数$ 2 $和指数$ P> 2 $（Mekler，J。Symb。Log。，1981）的图形组。特别是，我们的工作改善了Brachter＆Schweitzer的先前结果（LIC 2020）。 我们终于表明，$ Q $ - 无数卵石游戏也无法区分Abelian群体。这扩展了Grochow＆Levet（同上）的结果，后者在$ Q = 1 $的情况下建立了结果。一般主题是，将组同构置于$ \ textsf {p} $中似乎是必要的。
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 $\text{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 $\textsf{P}$ (Qiao, Sarma, & Tang, STACS 2011), and the complexity was recently improved to $\textsf{L}$ (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 $\textsf{P}$.
