Quadratic equations over free groups are NP-complete
arXiv:0802.3839 · doi:10.1007/s00224-008-9153-7
Abstract
We prove that the problems of deciding whether a quadratic equation over a free group has a solution is NP-complete.
arXiv:0802.3839 · doi:10.1007/s00224-008-9153-7
We prove that the problems of deciding whether a quadratic equation over a free group has a solution is NP-complete.