Knapsack problems in products of groups. (May 2016)

• Record Type: Journal Article
• Authors: Frenkel, Elizaveta; Nikolaev, Andrey; Ushakov, Alexander
• Is Part Of: Journal of symbolic computation. Volume 74(2016)
• Page Start: 96
• Page End: 108
• Publication Date: 2016-05
• Subjects: 03D15 -- 20F65 -- 20F10 -- 68Q45; Subset sum problem -- Knapsack problem -- Bounded subgroup membership problem -- Rational subset membership problem -- Free products -- Direct products -- Hyperbolic groups -- Nilpotent groups; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.05.006
• Languages: English
• ISSNs: 0747-7171

Abstract

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.