Quadratic Equations in Hyperbolic Groups are NP-complete

Olga Kharlampovich, Atefeh Mohajeri, Alex Taam +1

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|Q{|}^3$ for an ori…