Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
复制标题
2024 年年度 ACM-SIAM 离散算法研讨会 (SODA) 论文集
DOI：
10.1137/1.9781611977912.138
复制
发表时间：
2024
期刊：
影响因子：
--
通讯作者：
Dong R
中科院分区：
文献类型：
--
作者：
Dong R
设G是幂零类至多为10的单三角矩阵群。我们证明了单位问题（半群包含单位矩阵吗？）群问题（半群是群吗？）是多项式时间可判定的.我们的判定性结果也成立时，G是一个任意的类至多10个生成的幂零群。这扩展了巴拜等人关于交换矩阵群的早期工作（SODA'96）和Bell等人关于SL（2，1）的工作（SODA'17）。此外，我们给出了一个充分条件，使我们的结果推广到classd> 10的幂零群.对于每一个这样的，我们展示了一个有效的程序，验证这种情况下，它是真的。
LetGbe a unitriangular matrix group of nilpotency class at most ten. We show that the Identity Problem (does a semigroup contain the identity matrix?) and the Group Problem (is a semigroup a group?) are decidable in polynomial time for finitely generated subsemigroups ofG. Our decidability results also hold whenGis an arbitrary finitely generated nilpotent group of class at most ten. This extends earlier work of Babai et al. on commutative matrix groups (SODA’96) and work of Bell et al. onSL(2, ℤ) (SODA’17). Furthermore, we formulate a sufficient condition for the generalization of our results to nilpotent groups of classd> 10. For every suchd,we exhibit an effective procedure that verifies this condition in case it is true.