Knapsack problems for wreath products

DOI10.4230/LIPICS.STACS.2018.32MaRDI QIDQ3304131zbMATH OpenWikidataFDO

Authors Moses Ganardi, Markus Lohrey, Georg Zetzsche, D. König

Publication date 5 August 2020

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

zbMATH Keywords

decision problems in group theoryknapsackwreath products

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Extensions, wreath products, and other compositions of groups (20E22) 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)

Abstract: In recent years, knapsack problems for (in general non-commutative) groups have attracted attention. In this paper, the knapsack problem for wreath products is studied. It turns out that decidability of knapsack is not preserved under wreath product. On the other hand, the class of knapsack-semilinear groups, where solutions sets of knapsack equations are effectively semilinear, is closed under wreath product. As a consequence, we obtain the decidability of knapsack for free solvable groups. Finally, it is shown that for every non-trivial abelian group $G$, knapsack (as well as the related subset sum problem) for the wreath product $GwrmathbbZ$ is NP-complete.

Recommendations

• Knapsack in graph groups, HNN-extensions and amalgamated products
• Knapsack in graph groups
• Knapsack problems in products of groups
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Knapsack problems in groups

Cites work

• scientific article; zbMATH DE number 534859 (Why is no real title available?)
• Knapsack in graph groups, HNN-extensions and amalgamated products
• Knapsack problem for nilpotent groups
• Knapsack problems in groups
• Knapsack problems in products of groups
• On a theorem of Marshall Hall
• Reducibility among combinatorial problems
• Semigroups, Presburger formulas, and languages
• Subgroup distortion in wreath products of cyclic groups.
• Subset sum problem in polycyclic groups
• The co-word problem for the Higman-Thompson group is context-free
• The Complexity of Knapsack in Graph Groups
• The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\)

Cited in

(17)

• Lamplighter groups and automata
• Closure properties of knapsack semilinear groups
• scientific article; zbMATH DE number 7559438 (Why is no real title available?)
• Compressed decision problems in hyperbolic groups
• The power word problem
• Knapsack in hyperbolic groups
• Decidability problem for exponential equations in finitely presented groups
• Knapsack and the power word problem in solvable Baumslag–Solitar groups
• On subset sum problem in branch groups
• The power word problem in graph products
• Exponent equations in HNN-extensions
• Compressed decision problems in hyperbolic groups
• The complexity of knapsack problems in wreath products
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• A characterization of wreath products where knapsack is decidable
• On tropical knapsack-type problems
• Knapsack problems in products of groups

This page was built for publication: Knapsack problems for wreath products

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