TY - JOUR
T1 - Knapsack problems in groups
AU - Myasnikov, Alexei
AU - Nikolaev, Andrey
AU - Ushakov, Alexander
N1 - Publisher Copyright:
© 2014 American Mathematical Society.
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
KW - Baumslag's metabelian group
KW - Baumslag-Solitar group
KW - Bounded subgroup membership problem
KW - Hyperbolic groups
KW - Knapsack problem
KW - Metabelian groups
KW - Nilpotent groups
KW - Subset sum problem
KW - Thompson's group F
UR - http://www.scopus.com/inward/record.url?scp=84919363285&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84919363285&partnerID=8YFLogxK
U2 - 10.1090/S0025-5718-2014-02880-9
DO - 10.1090/S0025-5718-2014-02880-9
M3 - Article
AN - SCOPUS:84919363285
SN - 0025-5718
VL - 84
SP - 987
EP - 1016
JO - Mathematics of Computation
JF - Mathematics of Computation
IS - 292
ER -