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

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, DOI 10.1090/S0002-9947-05-03919-X
G. N. Arzhantseva, On quasiconvex subgroups of word hyperbolic groups, Geom. Dedicata 87 (2001), no. 1-3, 191–208. MR 1866849, DOI 10.1023/A:1012040207144
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, DOI 10.1007/978-3-662-12494-9
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
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, DOI 10.1016/0021-8693(81)90265-9
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, DOI 10.1142/S0218196794000105
Marc Culler, Using surfaces to solve equations in free groups, Topology 20 (1981), no. 2, 133–145. MR 605653, DOI 10.1016/0040-9383(81)90033-1
François Dahmani, Existential questions in (relatively) hyperbolic groups, Israel J. Math. 173 (2009), 91–124. MR 2570661, DOI 10.1007/s11856-009-0084-z
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).
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, DOI 10.1142/S0218196701000619
Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
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, DOI 10.1007/bf01058681
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, DOI 10.1142/S0218196792000153
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. MR 2114513, DOI 10.1145/335305.335308
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, DOI 10.1007/s00224-008-9153-7
Olga Kharlampovich and Alexei Myasnikov, Implicit function theorem over free groups, J. Algebra 290 (2005), no. 1, 1–203. MR 2154989, DOI 10.1016/j.jalgebra.2005.04.001
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, DOI 10.1142/S0218196711006704
M. Kufleitner, Wortgleichungen in hyperbolischen gruppen, Ph.D. thesis, Universität Stuttgart, Holzgartenstr. 16, 70174 Stuttgart, 2001.
I. G. Lysenok and A. G. Myasnikov, A polynomial bound for solutions of quadratic equations in free groups, Tr. Mat. Inst. Steklova 274 (2011), no. Algoritmicheskie Voprosy Algebry i Logiki, 148–190 (Russian, with Russian summary); English transl., Proc. Steklov Inst. Math. 274 (2011), no. 1, 136–173. MR 2962940, DOI 10.1134/S0081543811060101
G. S. Makanin, Equations in a free group, Izv. Akad. Nauk SSSR Ser. Mat. 46 (1982), no. 6, 1199–1273, 1344 (Russian). MR 682490
A. I. Mal′cev, 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
A. Yu. Ol′shanskiĭ, 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, DOI 10.1007/BF00970919
A. Yu. Ol′shanskiĭ, On residualing homomorphisms and $G$-subgroups of hyperbolic groups, Internat. J. Algebra Comput. 3 (1993), no. 4, 365–409. MR 1250244, DOI 10.1142/S0218196793000251
E. Rips and Z. Sela, Canonical representatives and equations in hyperbolic groups, Invent. Math. 120 (1995), no. 3, 489–512. MR 1334482, DOI 10.1007/BF01241140
Alina A. Vdovina, Constructing of orientable Wicks forms and estimation of their number, Comm. Algebra 23 (1995), no. 9, 3205–3222. MR 1335298, DOI 10.1080/00927879508825398
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, DOI 10.1017/S0308210500030626
Alina Vdovina, Products of commutators in free products, Internat. J. Algebra Comput. 7 (1997), no. 4, 471–485. MR 1459623, DOI 10.1142/S0218196797000216