Knapsack in hyperbolic groups

DOI10.1016/J.JALGEBRA.2019.04.008MaRDI QIDQ5919299zbMATH OpenOpenAlexWikidataFDO

Authors Markus Lohrey

Publication date 27 December 2019

Published in Journal of Algebra (Search for Journal in Brave)

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

zbMATH Keywords

hyperbolic groupsknapsack problems

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Hyperbolic groups and nonpositively curved groups (20F67) Analysis of algorithms and problem complexity (68Q25)

Abstract: Recently knapsack problems have been generalized from the integers to arbitrary finitely generated groups. The knapsack problem for a finitely generated group $G$ is the following decision problem: given a tuple $(g,g_1,ldots,g_k)$ of elements of $G$, are there natural numbers $n_1,ldots,n_{k}inmathbbN$ such that $g=g_1^{n_1}cdots{g}_k^{n_k}$ holds in $G$? Myasnikov, Nikolaev, and Ushakov proved that for every (Gromov-)hyperbolic group, the knapsack problem can be solved in polynomial time. In this paper, the precise complexity of the knapsack problem for hyperbolic group is determined: for every hyperbolic group $G$, the knapsack problem belongs to the complexity class $mathsfLogCFL$, and it is $mathsfLogCFL$-complete if $G$ contains a free group of rank two. Moreover, it is shown that for every hyperbolic group $G$ and every tuple $(g,g_1,ldots,g_k)$ of elements of $G$ the set of all $(n_1,ldots,n_k)inmathbb{N}^k$ such that $g=g_1^{n_1}cdots{g}_k^{n_k}$ in $G$ is semilinear and a semilinear representation where all integers are of size polynomial in the total geodesic length of the $g,g_1,ldots,g_k$ can be computed. Groups with this property are also called knapsack-tame. This enables us to show that knapsack can be solved in $mathsfLogCFL$ for every group that belongs to the closure of hyperbolic groups under free products and direct products with $mathbbZ$.

Recommendations

• Knapsack in hyperbolic groups
• Knapsack in graph groups
• Knapsack problems in products of groups
• Knapsack problem for nilpotent groups
• scientific article; zbMATH DE number 7139161
• Knapsack problems in groups
• Knapsack in graph groups, HNN-extensions and amalgamated products
• The Complexity of Knapsack in Graph Groups
• Cyclic group and knapsack facets
• Closure properties of knapsack semilinear groups

Cites work

• Algorithmic meta theorems for circuit classes of constant and logarithmic depth
• ALMOST EVERY GROUP IS HYPERBOLIC
• Compressed decision problems in hyperbolic groups
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Growing context-sensitive languages and Church-Rosser languages
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 1453080 (Why is no real title available?)
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Knapsack in graph groups
• Knapsack in graph groups, HNN-extensions and amalgamated products
• Knapsack problem for nilpotent groups
• Knapsack problems for wreath products
• Knapsack problems in groups
• Knapsack problems in products of groups
• On the Tape Complexity of Deterministic Context-Free Languages
• Reducibility among combinatorial problems
• Semigroups, Presburger formulas, and languages
• Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
• The co-word problem for the Higman-Thompson group is context-free
• The complexity of model checking (collapsible) higher-order pushdown systems
• THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS
• Verbal subgroups of hyperbolic groups have infinite width.
• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM

Cited in

(22)

• Knapsack in graph groups
• Closure properties of knapsack semilinear groups
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Knapsack in graph groups, HNN-extensions and amalgamated products
• The Complexity of Knapsack in Graph Groups
• scientific article; zbMATH DE number 7139161 (Why is no real title available?)
• scientific article; zbMATH DE number 7559438 (Why is no real title available?)
• Compressed decision problems in hyperbolic groups
• Knapsack problem for nilpotent groups
• Knapsack problems in groups
• Knapsack in hyperbolic groups
• Decidability problem for exponential equations in finitely presented groups
• Knapsack and the power word problem in solvable Baumslag–Solitar groups
• Post's Correspondence Problem for hyperbolic and virtually nilpotent groups
• Exponent equations in HNN-extensions
• Compressed decision problems in hyperbolic groups
• The complexity of knapsack problems in wreath products
• Membership problems in finite groups
• Membership problems in infinite groups
• 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 in hyperbolic groups

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