Knapsack problems in products of groups

DOI10.1016/J.JSC.2015.05.006zbMATH Open1401.20031arXiv1408.6509OpenAlexW1568867424MaRDI QIDQ898247FDOQ898247

Authors: N. E. Zubov 

Publication date: 8 December 2015

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

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.

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

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

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)

Cites Work

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

Cited In (22)

• Subset sum problem in polycyclic groups
• On subset sum problem in branch groups
• A relation between the knapsack and group knapsack problems
• Non-commutative lattice problems
• Closure properties of knapsack semilinear groups
• Knapsack problems in groups
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Knapsack in graph 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Magnus embedding and algorithmic properties of groups \(F/N^{(d)}\)
• Title not available (Why is that?)
• 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)