Knapsack problems in products of groups

DOI10.1016/j.jsc.2015.05.006zbMath1401.20031arXiv1408.6509OpenAlexW1568867424MaRDI QIDQ898247

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

free productsnilpotent groupshyperbolic groupsdirect productsknapsack problemsubset sum problemrational subset membership problembounded subgroup membership problem

Mathematics Subject Classification ID

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

Related Items

Non-commutative lattice problems, Subset sum problem in polycyclic groups, Decidability problem for exponential equations in finitely presented groups, Knapsack and the power word problem in solvable Baumslag–Solitar groups, Knapsack in graph groups, Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups, Closure properties of knapsack semilinear groups, Knapsack problem for nilpotent groups, Unnamed Item, Unnamed Item, Knapsack in hyperbolic groups, Magnus embedding and algorithmic properties of groups 𝐹/𝑁^{(𝑑)}, Solving a Mathematical Model for Small Vegetable Sellers in India by a Stochastic Knapsack Problem: An Advanced Genetic Algorithm Based Approach, Knapsack Problems for Wreath Products

Cites Work

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