Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 590

Preprint Number 590

Previous Next Preprint server

590. Olga Kharlampovich, Atefeh Mohajeri, Alex Taam, Alina Vdovina
Quadratic Equations in Hyperbolic Groups are NP-complete

Submission date: 4 June 2013.


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|^4 for an orientable equation and by N|Q|^{16} for a non-orientable equation, where |Q| is the length of the equation, and constant N can be computed. We show that the problem whether a quadratic equation in {\Gamma} has a solution, is NP-complete, and that there is a PSpace algorithm for solving arbitrary equations in {\Gamma}. We also give slightly larger bound for minimal solutions of quadratic equations in a toral relatively hyperbolic group.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 1306.0941: pdf, ps.

Last updated: June 7 2013 15:35 Please send your corrections to: