Quadratic equations in hyperbolic groups are NP-complete
From MaRDI portal
Publication:5267969
DOI10.1090/tran/6829zbMath1434.20020arXiv1306.0941OpenAlexW2963387703MaRDI QIDQ5267969
Atefeh Mohajeri, Alexander Taam, Alina Vdovina, O. G. Kharlampovich
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
Geometric group theory (20F65) Complexity of computation (including implicit computational complexity) (03D15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Hyperbolic groups and nonpositively curved groups (20F67)
Related Items (4)
Algorithmic undecidability of compatibility problem for equations in free groups: explicit equations with one commutator-type constraint ⋮ The Diophantine problem for systems of algebraic equations with exponents ⋮ Orientable quadratic equations in free metabelian groups ⋮ Explicit solutions of certain orientable quadratic equations in free groups
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Quadratic equations over free groups and free products
- The solvability problem for quadratic equations over free groups is NP-complete
- Using surfaces to solve equations in free groups
- Homomorphism diagrams of surface groups
- Canonical representatives and equations in hyperbolic groups
- Implicit function theorem over free groups.
- A polynomial bound on solutions of quadratic equations in free groups.
- Existential questions in (relatively) hyperbolic groups.
- LINEAR ESTIMATES FOR SOLUTIONS OF QUADRATIC EQUATIONS IN FREE GROUPS
- Satisfiability of equations in free groups is in PSPACE
- A DESCRIPTION OF SOLUTIONS OF QUADRATIC EQUATIONS IN HYPERBOLIC GROUPS
- ON RESIDUALING HOMOMORPHISMS AND G-SUBGROUPS OF HYPERBOLIC GROUPS
- PRODUCTS OF COMMUTATORS AND PRODUCTS OF SQUARES IN A FREE GROUP
- Products of Commutators in Free Products
- COMPUTATION IN WORD-HYPERBOLIC GROUPS
- Constructing of orientable wicks forms and estimation of their number
- On the number of nonorientable Wicks forms in a free group
- The computational complexity of knot genus and spanning area
- On quasiconvex subgroups of word hyperbolic groups
This page was built for publication: Quadratic equations in hyperbolic groups are NP-complete
