  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} \ldots u_d^{k_d}$, where $u_1, \ldots, u_d$ are
words over the group generators and $k_1, \ldots, k_d$ are binary encoded
integers, evaluate to the group identity?) and knapsack problem (does a given
equation $u_1^{x_1} \ldots u_d^{x_d} = v$, where $u_1, \ldots, u_d,v$ are words
over the group generators and $x_1,\ldots,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 \wr \mathbb{Z}$ with $G$ nilpotent and iterated wreath products
of free abelian groups belongs to $\mathsf{TC}^0$. As an application of the
latter, the power word problem for free solvable groups is in $\mathsf{TC}^0$.
On the other hand we show that for wreath products $G \wr \mathbb{Z}$, 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
$\mathsf{coNP}$-hard. For the knapsack problem we show
$\mathsf{NP}$-completeness for iterated wreath products of free abelian groups
and hence free solvable groups. Moreover, the knapsack problem for every wreath
product $G \wr \mathbb{Z}$, where $G$ is uniformly efficiently non-solvable, is
$\Sigma^2_p$-hard.
