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 P-time decidable in hyperbolic groups and give various examples of finitely presented groups where the subset sum problem is NP-complete.
| Original language | English |
|---|---|
| Pages (from-to) | 987-1016 |
| Number of pages | 30 |
| Journal | Mathematics of Computation |
| Volume | 84 |
| Issue number | 292 |
| DOIs | |
| State | Published - 2014 |
Keywords
- Baumslag's metabelian group
- Baumslag-Solitar group
- Bounded subgroup membership problem
- Hyperbolic groups
- Knapsack problem
- Metabelian groups
- Nilpotent groups
- Subset sum problem
- Thompson's group F
Fingerprint
Dive into the research topics of 'Knapsack problems in groups'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver