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?)

  • [1] Ian Agol, Joel Hass, and William Thurston, The computational complexity of knot genus and spanning area, Trans. Amer. Math. Soc. 358 (2006), no. 9, 3821-3850. MR 2219001, https://doi.org/10.1090/S0002-9947-05-03919-X
  • [2] G. N. Arzhantseva, On quasiconvex subgroups of word hyperbolic groups, Geom. Dedicata 87 (2001), no. 1-3, 191-208. MR 1866849, https://doi.org/10.1023/A:1012040207144
  • [3] Martin R. Bridson and André Haefliger, Metric spaces of non-positive curvature, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 319, Springer-Verlag, Berlin, 1999. MR 1744486
  • [4] Vladimir V. Chaynikov, Properties of hyperbolic groups: Free normal subgroups, quasiconvex subgroups and actions of maximal growth, ProQuest LLC, Ann Arbor, MI, 2012. Thesis (Ph.D.)-Vanderbilt University. MR 3121970
  • [5] Leo P. Comerford Jr. and Charles C. Edmunds, Quadratic equations over free groups and free products, J. Algebra 68 (1981), no. 2, 276-297. MR 608536, https://doi.org/10.1016/0021-8693(81)90265-9
  • [6] Leo P. Comerford Jr. and Charles C. Edmunds, Products of commutators and products of squares in a free group, Internat. J. Algebra Comput. 4 (1994), no. 3, 469-480. MR 1297152, https://doi.org/10.1142/S0218196794000105
  • [7] Marc Culler, Using surfaces to solve equations in free groups, Topology 20 (1981), no. 2, 133-145. MR 605653, https://doi.org/10.1016/0040-9383(81)90033-1
  • [8] François Dahmani, Existential questions in (relatively) hyperbolic groups, Israel J. Math. 173 (2009), 91-124. MR 2570661, https://doi.org/10.1007/s11856-009-0084-z
  • [9] F. Dahmani, V. Guirardel, and D. Osin, Hyperbolically embedded subgroups and rotating families in groups acting on hyperbolic spaces, to appear in Mem. Amer. Math. Soc., e-print arXiv:1111.7048 [math.GR] (2011).
  • [10] David B. A. Epstein and Derek F. Holt, Computation in word-hyperbolic groups, Internat. J. Algebra Comput. 11 (2001), no. 4, 467-487. MR 1850213, https://doi.org/10.1142/S0218196701000619
  • [11] Michael R. Garey and David S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. MR 519066
  • [12] R. I. Grigorchuk and P. F. Kurchanov, On quadratic equations in free groups, Proceedings of the International Conference on Algebra, Part 1 (Novosibirsk, 1989) Contemp. Math., vol. 131, Amer. Math. Soc., Providence, RI, 1992, pp. 159-171. MR 1175769
  • [13] R. I. Grigorchuk and I. G. Lysionok, A description of solutions of quadratic equations in hyperbolic groups, Internat. J. Algebra Comput. 2 (1992), no. 3, 237-274. MR 1189234, https://doi.org/10.1142/S0218196792000153
  • [14] Claudio Gutiérrez, Satisfiability of equations in free groups is in PSPACE, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, ACM, New York, 2000, pp. 21-27 (electronic). MR 2114513, https://doi.org/10.1145/335305.335308
  • [15] O. Kharlampovich, I. G. Lysënok, A. G. Myasnikov, and N. W. M. Touikan, The solvability problem for quadratic equations over free groups is NP-complete, Theory Comput. Syst. 47 (2010), no. 1, 250-258. MR 2643918, https://doi.org/10.1007/s00224-008-9153-7
  • [16] Olga Kharlampovich and Alexei Myasnikov, Implicit function theorem over free groups, J. Algebra 290 (2005), no. 1, 1-203. MR 2154989, https://doi.org/10.1016/j.jalgebra.2005.04.001
  • [17] Olga Kharlampovich and Alina Vdovina, Linear estimates for solutions of quadratic equations in free groups, Internat. J. Algebra Comput. 22 (2012), no. 1, 1250004, 16. MR 2900857, https://doi.org/10.1142/S0218196711006704
  • [18] M. Kufleitner, Wortgleichungen in hyperbolischen gruppen, Ph.D. thesis, Universität Stuttgart, Holzgartenstr. 16, 70174 Stuttgart, 2001.
  • [19] I. G. Lysenok and A. G. Myasnikov, A polynomial bound for solutions of quadratic equations in free groups, Tr. Mat. Inst. Steklova 274 (2011), 148-190 (Russian, with Russian summary); English transl., Proc. Steklov Inst. Math. 274 (2011), no. 1, 136-173. MR 2962940, https://doi.org/10.1134/S0081543811060101
  • [20] G. S. Makanin, Equations in a free group, Izv. Akad. Nauk SSSR Ser. Mat. 46 (1982), no. 6, 1199-1273, 1344 (Russian). MR 682490
  • [21] A. I. Malcev, On the equation $ zxyx^{-1}y^{-1}z^{-1}= aba^{-1}b^{-1}$ in a free group, Algebra i Logika Sem. 1 (1962), no. 5, 45-50 (Russian). MR 0153726
  • [22] A. Yu. Olshanskiĭ, Diagrams of homomorphisms of surface groups, Sibirsk. Mat. Zh. 30 (1989), no. 6, 150-171 (Russian); English transl., Siberian Math. J. 30 (1989), no. 6, 961-979 (1990). MR 1043443, https://doi.org/10.1007/BF00970919
  • [23] A. Yu. Olshanskiĭ, On residualing homomorphisms and $ G$-subgroups of hyperbolic groups, Internat. J. Algebra Comput. 3 (1993), no. 4, 365-409. MR 1250244, https://doi.org/10.1142/S0218196793000251
  • [24] E. Rips and Z. Sela, Canonical representatives and equations in hyperbolic groups, Invent. Math. 120 (1995), no. 3, 489-512. MR 1334482, https://doi.org/10.1007/BF01241140
  • [25] Alina A. Vdovina, Constructing of orientable Wicks forms and estimation of their number, Comm. Algebra 23 (1995), no. 9, 3205-3222. MR 1335298, https://doi.org/10.1080/00927879508825398
  • [26] A. Vdovina, On the number of nonorientable Wicks forms in a free group, Proc. Roy. Soc. Edinburgh Sect. A 126 (1996), no. 1, 113-116. MR 1378835, https://doi.org/10.1017/S0308210500030626
  • [27] Alina Vdovina, Products of commutators in free products, Internat. J. Algebra Comput. 7 (1997), no. 4, 471-485. MR 1459623, https://doi.org/10.1142/S0218196797000216

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