Quadratic equations in hyperbolic groups are NP-complete

Olga Kharlampovich, Atefeh Mohajeri, Alexander Taam, Alina Vdovina

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

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|3 for an orientable equation, and by N|Q|4 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.

Original languageEnglish
Pages (from-to)6207-6238
Number of pages32
JournalTransactions of the American Mathematical Society
Volume369
Issue number9
DOIs
StatePublished - 2017

Fingerprint

Dive into the research topics of 'Quadratic equations in hyperbolic groups are NP-complete'. Together they form a unique fingerprint.

Cite this