|
Knapsack problem for Baumslag–Solitar groups
F. A. Dudkinab, A. V. Treyerc a 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.
Received: 06.03.2018
Citation:
F. A. Dudkin, A. V. Treyer, “Knapsack problem for Baumslag–Solitar groups”, Sib. J. Pure and Appl. Math., 18:4 (2018), 43–55
Linking options:
https://www.mathnet.ru/eng/vngu484 https://www.mathnet.ru/eng/vngu/v18/i4/p43
|
|