{
  "id": "1807.06774",
  "version": "v1",
  "published": "2018-07-18T05:20:56.000Z",
  "updated": "2018-07-18T05:20:56.000Z",
  "title": "Knapsack in hyperbolic groups",
  "authors": [
    "Markus Lohrey"
  ],
  "categories": [
    "math.GR",
    "cs.FL"
  ],
  "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 \\in \\mathbb{N}$ 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 $\\mathsf{LogCFL}$, and it is $\\mathsf{LogCFL}$-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) \\in \\mathbb{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 $\\mathsf{LogCFL}$ for every group that belongs to the closure of hyperbolic groups under free products and direct products with $\\mathbb{Z}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-07-18T05:20:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20F10",
      "20F67"
    ],
    "keywords": [
      "hyperbolic group",
      "knapsack problem belongs",
      "total geodesic length",
      "complexity class",
      "direct products"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}