Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 

 

Knapsack problems in groups


Authors: Alexei Myasnikov, Andrey Nikolaev and Alexander Ushakov
Journal: Math. Comp. 84 (2015), 987-1016
MSC (2010): Primary 03D15, 20F65, 20F10
DOI: https://doi.org/10.1090/S0025-5718-2014-02880-9
Published electronically: July 30, 2014
MathSciNet review: 3290972
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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 $ \mathbf {P}$-time decidable in hyperbolic groups and give various examples of finitely presented groups where the subset sum problem is $ \mathbf {NP}$-complete.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 03D15, 20F65, 20F10

Retrieve articles in all journals with MSC (2010): 03D15, 20F65, 20F10


Additional Information

Alexei Myasnikov
Affiliation: Stevens Institute of Technology, Hoboken, New Jersey 07030
Email: amiasnik@stevens.edu

Andrey Nikolaev
Affiliation: Stevens Institute of Technology, Hoboken, New Jersey 07030
Email: anikolae@stevens.edu

Alexander Ushakov
Affiliation: Stevens Institute of Technology, Hoboken, New Jersey 07030
Email: aushakov@stevens.edu

DOI: https://doi.org/10.1090/S0025-5718-2014-02880-9
Keywords: Subset sum problem, knapsack problem, bounded subgroup membership problem, hyperbolic groups, Baumslag's metabelian group, nilpotent groups, metabelian groups, Baumslag-Solitar group, Thompson's group $F$.
Received by editor(s): March 29, 2012
Received by editor(s) in revised form: February 19, 2013, June 7, 2013, and July 1, 2013
Published electronically: July 30, 2014
Additional Notes: The work of the first and third authors was partially supported by NSF grant DMS-0914773.
Article copyright: © Copyright 2014 American Mathematical Society