摘要：We prove new complexity results for computational problems in certain wreath products of groups and (as an application) for free solvable groups. For a finitely generated group we study the so-called power word problem (does a given expression uâ,^{kâ,} ⦠u_d^{k_d}, where uâ,, â¦, u_d are words over the group generators and kâ,, â¦, k_d are binary encoded integers, evaluate to the group identity?) and knapsack problem (does a given equation uâ,^{xâ,} ⦠u_d^{x_d} = v, where uâ,, â¦, u_d,v are words over the group generators and xâ,,â¦,x_d are variables, have 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 TCâ°. As an application of the latter, the power word problem for free solvable groups is in TCâ°. 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 coNP-hard. For the knapsack problem we show NP-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 Σâ,,^p-hard.
关键词：algorithmic group theory; knapsack; wreath product
