Knapsack and the power word problem in solvable Baumslag–Solitar groups
Moses Ganardi, Markus Lohrey, Georg Zetzsche · International Journal of Algebra and Computation · 2023
We prove that the power word problem for certain metabelian subgroups of [Formula: see text] (including the solvable Baumslag–Solitar groups [Formula: see text]) belongs to the circuit complexity class [Formula: see text]. In the power word problem, the input consists of group elements [Formula: see text] and binary encoded integers [Formula: see text] and it is asked whether [Formula: see text] holds. Moreover, we prove that the knapsack problem for [Formula: see text] is [Formula: see text]-complete. In the knapsack problem, the input consists of group elements [Formula: see text] and it is asked whether the equation [Formula: see text] has a solution in [Formula: see text]. For the more general case of a system of so-called exponent equations, where the exponent variables [Formula: see text] can occur multiple times, we show that solvability is undecidable for [Formula: see text].