  In this paper we study the conjugacy problem in polycyclic groups. Our main
result is that we construct polycyclic groups $G_n$ whose conjugacy problem is
at least as hard as the subset sum problem with $n$ indeterminates. As such,
the conjugacy problem over the groups $G_n$ is NP-complete where the parameters
of the problem are taken in terms of $n$ and the length of the elements given
on input.
