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