Knapsack problems in products of groups

DOI10.1016/J.JSC.2015.05.006MaRDI QIDQ898247zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 8 December 2015

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.6509

zbMATH Keywords

knapsack problemdirect productsfree productsnilpotent groupshyperbolic groupssubset sum problemrational subset membership problembounded subgroup membership problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Generators, relations, and presentations of groups (20F05) Geometric group theory (20F65) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity of computation (including implicit computational complexity) (03D15)

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.

Recommendations

• Knapsack problems in groups
• Knapsack in graph groups, HNN-extensions and amalgamated products
• Knapsack in hyperbolic groups
• Knapsack problems for wreath products
• Knapsack in graph groups

Cites work

• scientific article; zbMATH DE number 5982274 (Why is no real title available?)
• scientific article; zbMATH DE number 3138253 (Why is no real title available?)
• scientific article; zbMATH DE number 1421044 (Why is no real title available?)
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Combinatorial group theory.
• Growth of finitely generated solvable groups and curvature of Riemannian manifolds
• Knapsack problems in groups
• Occurrence problem for braid groups \(B_{n+1}\) with \(n+1\geq 5\)
• On the rational subset problem for groups.
• Rational subsets of unitriangular groups.
• SOLVING THE WORD PROBLEM IN REAL TIME
• THE OCCURRENCE PROBLEM FOR FREE PRODUCTS OF GROUPS
• The Post correspondence problem in groups.
• Topological sorting of large networks

Cited in

(22)

• Subset sum problem in polycyclic groups
• On subset sum problem in branch groups
• Non-commutative lattice problems
• A relation between the knapsack and group knapsack problems
• Closure properties of knapsack semilinear groups
• Knapsack problems in groups
• Knapsack in graph groups
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Solving a Mathematical Model for Small Vegetable Sellers in India by a Stochastic Knapsack Problem: An Advanced Genetic Algorithm Based Approach
• Exponent equations in HNN-extensions
• Constrained inhomogeneous spherical equations: average-case hardness
• Decidability problem for exponential equations in finitely presented groups
• Knapsack and the power word problem in solvable Baumslag–Solitar groups
• Knapsack in hyperbolic groups
• Compressed decision problems in hyperbolic groups
• Knapsack problems for wreath products
• The Complexity of Knapsack in Graph Groups
• scientific article; zbMATH DE number 7559438 (Why is no real title available?)
• scientific article; zbMATH DE number 7559146 (Why is no real title available?)
• Magnus embedding and algorithmic properties of groups \(F/N^{(d)}\)
• scientific article; zbMATH DE number 7139161 (Why is no real title available?)
• Knapsack problem for nilpotent groups

This page was built for publication: Knapsack problems in products of groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q898247)