论文标题
在分支组中的子集总和问题
On subset sum problem in branch groups
论文作者
论文摘要
我们考虑经典子集总和问题的群体理论类似物。在此简短说明中，我们显示了第一个Grigorchuk组中的子集总和问题是NP库。更一般而言，我们在弱规则的分支组中显示了该问题的NP硬度，这意味着如果该组还签约，则表示NP的完整性。
We consider a group-theoretic analogue of the classic subset sum problem. In this brief note, we show that the subset sum problem is NP-complete in the first Grigorchuk group. More generally, we show NP-hardness of that problem in weakly regular branch groups, which implies NP-completeness if the group is, in addition, contracting.
