The solvability problem for quadratic equations over free groups is NP-complete

DOI10.1007/s00224-008-9153-7zbMath1205.68172arXiv0802.3839OpenAlexW2065138042MaRDI QIDQ987391

Nicholas W. M. Touikan, Igor G. Lysenok, O. G. Kharlampovich, Alexei G. Myasnikov

Publication date: 13 August 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenessequations over free groups

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algebraic geometry over groups; equations over groups (20F70)

Related Items (9)

Quadratic equations in metabelian Baumslag–Solitar groups ⋮ Orientable quadratic equations in free metabelian groups ⋮ A polynomial bound on solutions of quadratic equations in free groups. ⋮ On systems of equations over free partially commutative groups ⋮ Knapsack problems in groups ⋮ Explicit solutions of certain orientable quadratic equations in free groups ⋮ SLP compression for solutions of equations with constraints in free and hyperbolic groups ⋮ Quadratic equations in hyperbolic groups are NP-complete ⋮ Asymptotic invariants, complexity of groups and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quadratic equations over free groups and free products
• The singular case of the problem of absolute stability of systems of ordinary differential equations
• FANS AND LADDERS IN SMALL CANCELLATION THEORY
• A DESCRIPTION OF SOLUTIONS OF QUADRATIC EQUATIONS IN HYPERBOLIC GROUPS

This page was built for publication: The solvability problem for quadratic equations over free groups is NP-complete