Knapsack in hyperbolic groups

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)$ofelementsof$G$,aretherenaturalnumbers$n_1, \ldots, n_k \in $\mathbb{N}$$suchthat$g = g_1^{n_1} \cdots g_k^{n_k}$holdsin$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{L}\mathsf{o}\mathsf{g}\mathsf{C}\mathsf{F}\mathsf{L}$, and it is $\mathsf{L}\mathsf{o}\mathsf{g}\mathsf{C}\mathsf{F}\mathsf{L}$-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,\dots ,g_k)$ of elements of $G$ the set of all $(n_1,\dots ,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{L}\mathsf{o}\mathsf{g}\mathsf{C}\mathsf{F}\mathsf{L}$ for every group that belongs to the closure of hyperbolic groups under free products and direct products with $\mathbb{Z}$.