Elizaveta Frenkel, Andrey Nikolaev, Alexander Ushakov
Published 2014-08-27Version 1
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.
Comments: 12 pages, 5 figures
Knapsack Problems in Groups
Sigma Invariants of Direct Products of Groups
Direct products of free groups in ${\rm{Aut}}(F_N)$
![QR code for arXiv:1408.6509 [math.GR]](http://oss.arxitics.com/images/favicon.svg)