TY - JOUR
T1 - Knapsack problems in products of groups
AU - Frenkel, Elizaveta
AU - Nikolaev, Andrey
AU - Ushakov, Alexander
N1 - Publisher Copyright:
© 2015 Elsevier Ltd.
PY - 2016/5
Y1 - 2016/5
N2 - 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.
AB - 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.
KW - Bounded subgroup membership problem
KW - Direct products
KW - Free products
KW - Hyperbolic groups
KW - Knapsack problem
KW - Nilpotent groups
KW - Rational subset membership problem
KW - Subset sum problem
UR - http://www.scopus.com/inward/record.url?scp=84948712241&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84948712241&partnerID=8YFLogxK
U2 - 10.1016/j.jsc.2015.05.006
DO - 10.1016/j.jsc.2015.05.006
M3 - Article
AN - SCOPUS:84948712241
SN - 0747-7171
VL - 74
SP - 96
EP - 108
JO - Journal of Symbolic Computation
JF - Journal of Symbolic Computation
ER -