Quadratic equations over free groups are NP-complete
  We prove that the problems of deciding whether a quadratic equation over a free group has a solution is NP-complete. 
O. Kharlampovich, I.G. Lysenok, A.G Myasnikov, N.W.M. Touikan