Subset sum problem in polycyclic groups. (January 2018) - Nikolaev, Andrey; Ushakov, Alexander
Abstract: We consider a group-theoretic analogue of the classic subset sum problem. It is known that every virtually nilpotent group has polynomial time decidable subset sum problem. In this paper we use subgroup distortion to show that every polycyclic non-virtually-nilpotent group hasNP -complete subset sum problem.