Knapsack problems in products of groups
arXiv:1408.6509 · doi:10.1016/j.jsc.2015.05.006
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.
15 pages, 5 figures. Updated to include more general results, mostly in Section 4
Cited by in corpus (8)
- Knapsack in graph groups, HNN-extensions and amalgamated products
- Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
- Closure properties of knapsack semilinear groups
- Exponential equations in acylindrically hyperbolic groups
- Notes about decidability of exponential equations
- Knapsack in hyperbolic groups
- The Complexity of Knapsack in Graph Groups
- Exponent equations in HNN-extensions