Knapsack Problems for Wreath Products

被引：10

作者：

Ganardi, Moses ^{[1
]}

Koenig, Daniel ^{[1
]}

Lohrey, Markus ^{[1
]}

Zetzsche, Georg ^{[2
,3
]}

机构：

[1] Univ Siegen, Siegen, Germany

[2] CNRS, LSV, Paris, France

[3] ENS Paris Saclay, Paris, France

来源：

35TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2018) | 2018年 / 96卷

关键词：

Knapsack; Wreath Products; Decision Problems in Group Theory;

D O I：

10.4230/LIPIcs.STACS.2018.32

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In recent years, knapsack problems for (in general non-commutative) groups have attracted attention. In this paper, the knapsack problem for wreath products is studied. It turns out that decidability of knapsack is not preserved under wreath product. On the other hand, the class of knapsack-semilinear groups, where solutions sets of knapsack equations are effectively semilinear, is closed under wreath product. As a consequence, we obtain the decidability of knapsack for free solvable groups. Finally, it is shown that for every non-trivial abelian group G, knapsack (as well as the related subset sum problem) for the wreath product G (sic) Z is NP-complete.

引用

页数：13

共 18 条

[1] Subgroup distortion in wreath products of cyclic groups [J].