Quadratic equations over free groups are NP-complete

arxiv: 0802.3839 · v1 · pith:K3HQ3JP5new · submitted 2008-02-26 · 🧮 math.GR

O. Kharlampovich , I.G. Lysenok , A.G Myasnikov , N.W.M. Touikan This is my paper

classification 🧮 math.GR

keywords freenp-completequadraticdecidingequationequationsgroupgroups

0 comments

read the original abstract

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

This paper has not been read by Pith yet.