Quadratic equations in hyperbolic groups are NP-complete

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

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)

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

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.

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

• 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
• Hyperbolic Surfaces and Quadratic Equations in 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)