math.GR
Knapsack and the power word problem in solvable Baumslag Solitar groups. We prove that the power word problem for the solvable Baumslag Solitar groups mathsf BS (1,q) langle a,t mid t a t 1 a q rangle can be solved in mathsf TC 0 . In the power word problem, the input consists of group elements g 1, ldots, g d and binary encoded integers n 1, ldots, 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, ldots, 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 .