2026-07-22T07:05:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13656 2024-03-06T10:52:35Z ddc:004 open_access

A Characterization of Wreath Products Where Knapsack Is Decidable Bergsträßer, Pascal Ganardi, Moses Zetzsche, Georg knapsack wreath products decision problems in group theory decidability discrete Heisenberg group Baumslag-Solitar groups The knapsack problem for groups was introduced by Miasnikov, Nikolaev, and Ushakov. It is defined for each finitely generated group G and takes as input group elements g_1,…,g_n,g ∈ G and asks whether there are x_1,…,x_n ≥ 0 with g_1^{x_1}⋯ g_n^{x_n} = g. We study the knapsack problem for wreath products G≀H of groups G and H. Our main result is a characterization of those wreath products G≀H for which the knapsack problem is decidable. The characterization is in terms of decidability properties of the indiviual factors G and H. To this end, we introduce two decision problems, the intersection knapsack problem and its restriction, the positive intersection knapsack problem. Moreover, we apply our main result to H₃(ℤ), the discrete Heisenberg group, and to Baumslag-Solitar groups BS(1,q) for q ≥ 1. First, we show that the knapsack problem is undecidable for G≀H₃(ℤ) for any G ≠ 1. This implies that for G ≠ 1 and for infinite and virtually nilpotent groups H, the knapsack problem for G≀H is decidable if and only if H is virtually abelian and solvability of systems of exponent equations is decidable for G. Second, we show that the knapsack problem is decidable for G≀BS(1,q) if and only if solvability of systems of exponent equations is decidable for G. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pascal Bergsträßer and Moses Ganardi and Georg Zetzsche 2021 Is Part Of LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2021.11 urn:nbn:de:0030-drops-136566 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.11 eng https://creativecommons.org/licenses/by/4.0/legalcode