MODNET

Research Training Network in Model Theory

Publications > Preprint server > Preprint Number 590
Preprint Number 590
590. Olga Kharlampovich, Atefeh Mohajeri, Alex Taam, Alina Vdovina Quadratic Equations in Hyperbolic Groups are NP-complete E-mail: Submission date: 4 June 2013. Abstract: 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: |

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