Knapsack problem for Baumslag–Solitar groups

F. A. Dudkin^ab, A. V. Treyer<sup>c

a</sup> Novosibirsk State University
^b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
^c Omsk State Technical University

Abstract: In this work we investigate a decidability problem of group version of the knapsack problem for the Baumslag–Solitar group $BS(p,q)$. We proved, that the knapsack problem is decidable for the group $BS(p,q)$ for coprime integers $p > 1$, $q > 1$. In the case where $p=1$, $q\in \mathbb{N}$, we proved that the knapsack problem is decidable for the group $BS(1,q)$ with some restriction on the input of the problem. However, the problem of the decidability of the knapsack problem for the group $BS(1,q)$ on the whole set of inputs remains open.

Keywords: Baumslag–Solitar group, knapsack problem, decidability.

UDC: 512.543

Received: 06.03.2018

DOI: 10.33048/pam.2018.18.404