Knapsack and the power word problem in solvable Baumslag–Solitar groups.

We prove that the power word problem for certain metabelian subgroups of G L (2 , ℂ) (including the solvable Baumslag–Solitar groups BS (1 , q) = 〈 a , t | t a t − 1 = a q 〉) belongs to the circuit complexity class T C 0 . In the power word problem, the input consists of group elements g 1 , ... , g d and binary encoded integers n 1 , ... , n d and it is asked whether g 1 n 1 ⋯ g d n d = 1 holds. Moreover, we prove that the knapsack problem for BS (1 , q) is N P -complete. In the knapsack problem, the input consists of group elements g 1 , ... , g d , h and it is asked whether the equation g 1 x 1 ⋯ g d x d = h has a solution in ℕ 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 BS (1 , q). [ABSTRACT FROM AUTHOR]