A family of polycyclic groups over which the uniform conjugacy problem   is NP-complete
  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. 
Bren Cavallo and Delaram Kahrobaei
math.GR cs.CC cs.CR