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

DOI10.1007/S00224-008-9153-7MaRDI QIDQ987391zbMATH OpenOpenAlexFDO

Authors Olga Kharlampovich, Igor Lysenok, Alexei Myasnikov, Nicholas W. M. Touikan

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

equations over free groupsNP-completeness

Mathematics Subject Classification ID

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

Abstract: We prove that the problems of deciding whether a quadratic equation over a free group has a solution is NP-complete.

Cites work

• A DESCRIPTION OF SOLUTIONS OF QUADRATIC EQUATIONS IN HYPERBOLIC GROUPS
• FANS AND LADDERS IN SMALL CANCELLATION THEORY
• 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 1408356 (Why is no real title available?)
• Quadratic equations over free groups and free products
• The singular case of the problem of absolute stability of systems of ordinary differential equations

Cited in

(14)

• 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.
• Asymptotic invariants, complexity of groups and related problems.
• 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
• Knapsack problems in groups
• Quadratic equations in metabelian Baumslag–Solitar groups
• Constrained inhomogeneous spherical equations: average-case hardness
• Orientable quadratic equations in wreath products of abelian groups
• Quadratic equations in the lamplighter group
• Solving one variable word equations in the free group in cubic time
• Quadratic equations in graph products of groups and the exponent of periodicity

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

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