  In this work we introduce a new succinct variant of the word problem in a
finitely generated group $G$, which we call the power word problem: the input
word may contain powers $p^x$, where $p$ is a finite word over generators of
$G$ and $x$ is a binary encoded integer. The power word problem is a
restriction of the compressed word problem, where the input word is represented
by a straight-line program (i.e., an algebraic circuit over $G$). The main
result of the paper states that the power word problem for a finitely generated
free group $F$ is AC$^0$-Turing-reducible to the word problem for $F$.
Moreover, the following hardness result is shown: For a wreath product $G \wr
\mathbb{Z}$, where $G$ is either free of rank at least two or finite
non-solvable, the power word problem is complete for coNP. This contrasts with
the situation where $G$ is abelian: then the power word problem is shown to be
in TC$^0$.

Group Theory;Computational Complexity