Knapsack and the power word problem in solvable Baumslag-Solitar groups

Abstract

We prove that the power word problem for certain metabelian subgroups of $\mathsf{GL}(2,\mathbb{C})$ (including the solvable Baumslag-Solitar groups $\mathsf{BS}(1,q)=⟨a,t\mid ta{t}^{-1}=a^q⟩$) belongs to the circuit complexity class ${\mathsf{TC}}^0$. In the power word problem, the input consists of group elements $g_1,\dots ,g_d$ and binary encoded integers $n_1,\dots ,n_d$ and it is asked whether $g_1^{n_1}\cdots g_d^{n_d}=1$ holds. Moreover, we prove that the knapsack problem for $\mathsf{BS}(1,q)$ is $\mathsf{NP}$-complete. In the knapsack problem, the input consists of group elements $g_1,\dots ,g_d,h$ and it is asked whether the equation $g_1^{x_1}\cdots g_d^{x_d}=h$ has a solution in ${\mathbb{N}}^d$. For the more general case of a system of so-called exponent equations, where the exponent variables $x_i$ can occur multiple times, we show that solvability is undecidable for $\mathsf{BS}(1,q)$.

A short version appeared in the proceedings of MFCS 2020