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 , the length of the value of each variable in a minimal solution of a quadratic equation
is bounded by
for an orientable equation, and by
for a non-orientable equation, where
is the length of the equation and the constant
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.
- [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
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
-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
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