Quadratic equations in hyperbolic groups are NP-complete

Kharlampovich, Olga; Mohajeri, Atefeh; Taam, Alexander; Vdovina, Alina

doi:10.1090/tran/6829

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 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 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.

[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 -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