Abstract
The classic knapsack and related problems have natural generalizations to arbitrary (non-commutative) groups, collectively called knapsack-type problems in groups. We study the effect of free and direct products on their time complexity. We show that free products in certain sense preserve time complexity of knapsack-type problems, while direct products may amplify it. Our methods allow to obtain complexity results for rational subset membership problem in amalgamated free products over finite subgroups.
| Original language | English |
|---|---|
| Pages (from-to) | 96-108 |
| Number of pages | 13 |
| Journal | Journal of Symbolic Computation |
| Volume | 74 |
| DOIs | |
| State | Published - May 2016 |
Keywords
- Bounded subgroup membership problem
- Direct products
- Free products
- Hyperbolic groups
- Knapsack problem
- Nilpotent groups
- Rational subset membership problem
- Subset sum problem
Fingerprint
Dive into the research topics of 'Knapsack problems in products of groups'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver