Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
It is shown that the knapsack problem (introduced by Myasnikov, Nikolaev, and Ushakov) is undecidable in a direct product of sufficiently many copies of the discrete Heisenberg group (which is nilpotent of class 2). Moreover, for the discrete Heisenberg group itself, the knapsack problem is decidable. Hence, decidability of the …