论文标题
改进了Baumslag组的平行算法
Improved Parallel Algorithms for Baumslag Groups
论文作者
论文摘要
Baumslag Group一直是一个非常困难的单词问题的小组的候选人，直到Myasnikov，Ushakov，Won成功地证明了它的单词问题可以在多项式时期解决。他们的结果使用了新开发的电路数据结构，允许对整数进行非元素压缩。后来，这是两个方向扩展的：劳恩表明，对于$ q \ geq 2 $，baumslag组$ g_ {1，q} $，我们确定Baumslag组$ g_ {1，2} $的单词问题可以在$ \ mathsf {tc {tc}^2 $中解决。 在这项工作中，我们完善了减少功率电路的操作，以进一步改善这两个结果。我们证明了baumslag组的单词问题$ g_ {p，pq} $ with $ | p |，| q | \ geq 1 $可以用$ \ mathsf {utc}^1 $解决。此外，我们证明了$ g_ {p，pq} $中的共轭问题在$ \ mathsf {utc}^1 $中非常普遍（这意味着对于“大多数”输入，它是$ \ mathsf {utc}^1 $）。最后，对于g_ {1，q} $中的每一个固定的$ g \（case $ p = 1 $）与$ g $的共轭可以在$ \ mathsf {utc}^1 $中为所有输入确定。 我们进一步表明，如果输入单词以相当压缩的形式给出，那么Baumslag-Solitar-Solitar-Solitar-Solitar-Solitar-solitar-solitar $ bs_ {p，pq} $在$ \ mathsf {uac}^0（f_2）$中，因此给这些组的特定词语问题给出了复杂性结果。
The Baumslag group had been a candidate for a group with an extremely difficult word problem until Myasnikov, Ushakov, and Won succeeded to show that its word problem can be solved in polynomial time. Their result used the newly developed data structure of power circuits allowing for a non-elementary compression of integers. Later this was extended in two directions: Laun showed that the same applies to the Baumslag groups $G_{1, q}$ for $q \geq 2$ and we established that the word problem of the Baumslag group $G_{1, 2}$ can be solved in $\mathsf{TC}^2$. In this work we refine the operations on reduced power circuits to further improve upon both results. We show that the word problem of the Baumslag groups $G_{p, pq}$ with $|p|,|q| \geq 1$ can be solved in $\mathsf{uTC}^1$. Moreover, we prove that the conjugacy problem in $G_{p, pq}$ is strongly generically in $\mathsf{uTC}^1$ (meaning that for "most" inputs it is in $\mathsf{uTC}^1$). Finally, for every fixed $g \in G_{1, q}$ (case $p=1$) conjugacy to $g$ can be decided in $\mathsf{uTC}^1$ for all inputs. We further show that the word problem of the Baumslag-Solitar groups $BS_{p, pq}$ is in $\mathsf{uAC}^0(F_2)$ if the input word is given in a quite compressed form and so give a complexity result for a special case of the power word problem for these groups.
