Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Quadratic equations in hyperbolic groups are NP-complete
HTML articles powered by AMS MathViewer

by Olga Kharlampovich, Atefeh Mohajeri, Alexander Taam and Alina Vdovina PDF
Trans. Amer. Math. Soc. 369 (2017), 6207-6238 Request permission

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|^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 $\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
Similar Articles
Additional Information
  • Olga Kharlampovich
  • Affiliation: Department of Mathematics and Statistics, Hunter College, CUNY, 695 Park Avenue, New York, New York 10065
  • MR Author ID: 191704
  • Email: okharlampovich@gmail.com
  • Atefeh Mohajeri
  • Affiliation: Department of Mathematics and Statistics, McGill University, 805 Sherbrooke Street W., Montreal H3A 0B9, Canada
  • MR Author ID: 885924
  • 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
  • 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
  • © Copyright 2017 American Mathematical Society
  • 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
  • MathSciNet review: 3660218