Quadratic equations in hyperbolic groups are NP-complete

DOI10.1090/TRAN/6829MaRDI QIDQ5267969zbMATH OpenOpenAlexFDO

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

Publication date 14 June 2017

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

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)

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.

Recommendations

• A DESCRIPTION OF SOLUTIONS OF QUADRATIC EQUATIONS IN HYPERBOLIC GROUPS
• Hyperbolic Surfaces and Quadratic Equations in Groups
• Equations in the Q-completion of a torsion-free hyperbolic group
• Linear estimates for solutions of quadratic equations in free groups.
• SLP compression for solutions of equations with constraints in free and hyperbolic groups.

Cites work

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

Cited in

(10)

• Algorithmic undecidability of compatibility problem for equations in free groups: explicit equations with one commutator-type constraint
• Quadratic equations in the Grigorchuk group.
• Explicit solutions of certain orientable quadratic equations in free groups
• Constrained inhomogeneous spherical equations: average-case hardness
• Orientable quadratic equations in free metabelian groups
• SLP compression for solutions of equations with constraints in free and hyperbolic groups.
• A DESCRIPTION OF SOLUTIONS OF QUADRATIC EQUATIONS IN HYPERBOLIC GROUPS
• Hyperbolic Surfaces and Quadratic Equations in Groups
• The Diophantine problem for systems of algebraic equations with exponents
• Quadratic equations in metabelian Baumslag–Solitar groups

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)