Quadratic equations in hyperbolic groups are NP-complete

DOI10.1090/TRAN/6829zbMATH Open1434.20020arXiv1306.0941OpenAlexW2963387703MaRDI QIDQ5267969FDOQ5267969

Atefeh Mohajeri, Alexander Taam, Alina Vdovina, Olga Kharlampovich

Publication date: 14 June 2017

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1306.0941

Mathematics Subject Classification ID

Geometric group theory (20F65) Hyperbolic groups and nonpositively curved groups (20F67) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• PRODUCTS OF COMMUTATORS AND PRODUCTS OF SQUARES IN A FREE GROUP
• Products of Commutators in Free Products
• Title not available (Why is that?)
• On the number of nonorientable Wicks forms in a free group
• Quadratic equations over free groups and free products
• On quasiconvex subgroups of word hyperbolic groups
• Canonical representatives and equations in hyperbolic groups
• Satisfiability of equations in free groups is in PSPACE
• Using surfaces to solve equations in free groups
• ON RESIDUALING HOMOMORPHISMS AND G-SUBGROUPS OF HYPERBOLIC GROUPS
• Homomorphism diagrams of surface groups
• Implicit function theorem over free groups.
• The computational complexity of knot genus and spanning area
• COMPUTATION IN WORD-HYPERBOLIC GROUPS
• Title not available (Why is that?)
• Existential questions in (relatively) hyperbolic groups.
• Constructing of orientable wicks forms and estimation of their number
• A DESCRIPTION OF SOLUTIONS OF QUADRATIC EQUATIONS IN HYPERBOLIC GROUPS
• The solvability problem for quadratic equations over free groups is NP-complete
• A polynomial bound on solutions of quadratic equations in free groups.
• Linear estimates for solutions of quadratic equations in free groups.

Cited In (6)

• Algorithmic undecidability of compatibility problem for equations in free groups: explicit equations with one commutator-type constraint
• Explicit solutions of certain orientable quadratic equations in free groups
• Constrained inhomogeneous spherical equations: average-case hardness
• Orientable quadratic equations in free metabelian groups
• A DESCRIPTION OF SOLUTIONS OF QUADRATIC EQUATIONS IN HYPERBOLIC GROUPS
• The Diophantine problem for systems of algebraic equations with exponents

This page was built for publication: Quadratic equations in hyperbolic groups are NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5267969)