arXiv Analytics

Sign in

arXiv:1302.5671 [math.GR]AbstractReferencesReviewsResources

Knapsack Problems in Groups

Alexei Myasnikov, Andrey Nikolaev, Alexander Ushakov

Published 2013-02-22Version 1

We generalize the classical knapsack and subset sum problems to arbitrary groups and study the computational complexity of these new problems. We show that these problems, as well as the bounded submonoid membership problem, are P-time decidable in hyperbolic groups and give various examples of finitely presented groups where the subset sum problem is NP-complete.

Related articles: Most relevant | Search more
arXiv:1408.6509 [math.GR] (Published 2014-08-27)
Knapsack problems in products of groups
arXiv:2107.04985 [math.GR] (Published 2021-07-11)
Research announcement: A combination theorem for acylindrical complexes of hyperbolic groups and Cannon-Thurston maps
arXiv:1605.00598 [math.GR] (Published 2016-05-02)
Computational complexity and the conjugacy problem