The complexity of knapsack problems in wreath products
share
We prove new complexity results for computational problems in certain wreath products of groups and (as an application) for free solvable group. For a finitely generated group we study the so-called power word problem (does a given expression u_1^k_1... u_d^k_d, where u_1, ..., u_d are words over the group generators and k_1, ..., k_d are binary encoded integers, evaluate to the group identity?) and knapsack problem (does a given equation u_1^x_1... u_d^x_d = v, where u_1, ..., u_d,v are words over the group generators and x_1,...,x_d are variables, has a solution in the natural numbers). We prove that the power word problem for wreath products of the form G ≀ℤ with G nilpotent and iterated wreath products of free abelian groups belongs to 𝖳𝖢^0. As an application of the latter, the power word problem for free solvable groups is in 𝖳𝖢^0. On the other hand we show that for wreath products G ≀ℤ, where G is a so called uniformly strongly efficiently non-solvable group (which form a large subclass of non-solvable groups), the power word problem is 𝖼𝗈𝖭𝖯-hard. For the knapsack problem we show 𝖭𝖯-completeness for iterated wreath products of free abelian groups and hence free solvable groups. Moreover, the knapsack problem for every wreath product G ≀ℤ, where G is uniformly efficiently non-solvable, is Σ^2_p-hard.
READ FULL TEXT