QUADRATIC EQUATIONS IN HYPERBOLIC GROUPS ARE NP-COMPLETE

We prove that in a torsion-free hyperbolic group Gamma, the length of the value of each variable in a minimal solution of a quadratic equation Q = 1 is bounded by N vertical bar Q vertical bar(3) for an orientable equation, and by N vertical bar Q vertical bar(4) for a nonorientable equation, where vertical bar Q vertical bar is the length of the equation and the constant N can be computed. We show that the problem, whether a quadratic equation in G has a solution, is in NP, and that there is a PSpace algorithm for solving arbitrary equations in Gamma. If additionally Gamma 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.