TY - JOUR
T1 - Quadratic equations in hyperbolic groups are NP-complete
AU - Kharlampovich, Olga
AU - Mohajeri, Atefeh
AU - Taam, Alexander
AU - Vdovina, Alina
N1 - Publisher Copyright:
© 2017 American Mathematical Society.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85020480047&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85020480047&partnerID=8YFLogxK
U2 - 10.1090/tran/6829
DO - 10.1090/tran/6829
M3 - Article
AN - SCOPUS:85020480047
SN - 0002-9947
VL - 369
SP - 6207
EP - 6238
JO - Transactions of the American Mathematical Society
JF - Transactions of the American Mathematical Society
IS - 9
ER -