Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups

Daniel König, Markus Lohrey, Georg Zetzsche

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 gro…