DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2021.11

A Characterization of Wreath Products Where Knapsack Is Decidable

Authors: Pascal Bergsträßer, Moses Ganardi, and Georg Zetzsche

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract

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.

Cite as

Pascal Bergsträßer, Moses Ganardi, and Georg Zetzsche. A Characterization of Wreath Products Where Knapsack Is Decidable. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bergstraer_et_al:LIPIcs.STACS.2021.11,
  author =	{Bergstr\"{a}{\ss}er, Pascal and Ganardi, Moses and Zetzsche, Georg},
  title =	{{A Characterization of Wreath Products Where Knapsack Is Decidable}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.11},
  URN =		{urn:nbn:de:0030-drops-136566},
  doi =		{10.4230/LIPIcs.STACS.2021.11},
  annote =	{Keywords: knapsack, wreath products, decision problems in group theory, decidability, discrete Heisenberg group, Baumslag-Solitar groups}
}

Search Results

Documents authored by Bergsträßer, Pascal

A Characterization of Wreath Products Where Knapsack Is Decidable

Abstract

Cite as

Thanks for your feedback!

Could not send message