Quadratic equations in hyperbolic groups are NP-complete

We prove that in a torsion-free hyperbolic group Γ, the length of the value of each variable in a minimal solution of a quadratic equation Q = 1 is bounded by N|Q|³ for an orientable equation, and by N|Q|⁴ for a non- orientable equation, where |Q| is the length of the equation and the constant N can be computed. We show that the problem, whether a quadratic equation in Γ has a solution, is in NP, and that there is a PSpace algorithm for solving arbitrary equations in Γ. If additionally Γ is non-cyclic, then this problem (of deciding existence of a solution) is NP-complete. We also give a slightly larger bound for minimal solutions of quadratic equations in a toral relatively hyperbolic group.