Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Quadratic equations in hyperbolic groups are NP-complete


Authors: Olga Kharlampovich, Atefeh Mohajeri, Alexander Taam and Alina Vdovina
Journal: Trans. Amer. Math. Soc. 369 (2017), 6207-6238
MSC (2010): Primary 20F10, 20F65, 20F67; Secondary 03D15
DOI: https://doi.org/10.1090/tran/6829
Published electronically: February 13, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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\vert Q\vert^3$ for an orientable equation, and by $ N\vert Q\vert^{4}$ for a non-orientable equation, where $ \vert Q\vert$ is the length of the equation and the constant $ N$ can be computed. We show that the problem, whether a quadratic equation in $ \Gamma $ has a solution, is in NP, and that there is a PSpace algorithm for solving arbitrary equations in $ \Gamma $. If additionally $ \Gamma $ 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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 20F10, 20F65, 20F67, 03D15

Retrieve articles in all journals with MSC (2010): 20F10, 20F65, 20F67, 03D15


Additional Information

Olga Kharlampovich
Affiliation: Department of Mathematics and Statistics, Hunter College, CUNY, 695 Park Avenue, New York, New York 10065
Email: okharlampovich@gmail.com

Atefeh Mohajeri
Affiliation: Department of Mathematics and Statistics, McGill University, 805 Sherbrooke Street W., Montreal H3A 0B9, Canada
Email: at.mohajeri@gmail.com

Alexander Taam
Affiliation: Department of Mathematics, Graduate Center, CUNY, 365 Fifth Avenue, New York, New York 10016
Address at time of publication: Department of Mathematical Sciences, Stevens Institute of Technology, Hoboken, New Jersey 07030
Email: alex.taam@gmail.com

Alina Vdovina
Affiliation: School of Mathematics and Statistics, Newcastle University, Newcastle upon Tyne, NE1 7RU, United Kingdom
Email: Alina.Vdovina@newcastle.ac.uk

DOI: https://doi.org/10.1090/tran/6829
Received by editor(s): July 9, 2014
Received by editor(s) in revised form: May 11, 2015, and September 16, 2015
Published electronically: February 13, 2017
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society