2026-08-15T19:02:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8520 2024-03-06T10:42:19Z ddc:004 open_access

Knapsack Problems for Wreath Products Ganardi, Moses König, Daniel Lohrey, Markus Zetzsche, Georg knapsack wreath products decision problems in group theory 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 \wr Z is NP-complete. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moses Ganardi and Daniel König and Markus Lohrey and Georg Zetzsche 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.32 urn:nbn:de:0030-drops-85201 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.32 eng https://creativecommons.org/licenses/by/3.0/legalcode