Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4945917 | Journal of Symbolic Computation | 2018 | 11 Pages |
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 has NP-complete subset sum problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Andrey Nikolaev, Alexander Ushakov,